{ }codelper
referencesstandard containersbinary searchP0125

Fix by reference, find with lower_bound

Store the name, price and stock of n items in a std::vector of structs, change them with m commands, then answer q queries. The function that finds an item by name returns the element inside the vector as a reference (Item&), and the function that changes an item takes that reference and changes the element in place. After all commands, sort with std::sort and a lambda comparator by price from low to high, and by name in dictionary order on equal prices.
Answer queries with std::lower_bound. The first line has n, and the next n lines have "name price stock". The next line has m, and the next m lines each have a command: "sell name k", "restock name k" or "price name p". sell subtracts k from the stock if there are at least k; otherwise it changes nothing.
restock adds k to the stock.
price changes the price to p. The next line has q, and the next q lines have one integer x each. For each query, print the number c of items in the sorted list whose price is lower than x, and the first item whose price is at least x, as "c name price stock".
If there is no such item, print "c none".

Input
1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000, 1 ≤ q ≤ 1000.
Names are 1 to 8 lowercase English letters, all different, and commands use only existing names.
1 ≤ price, p ≤ 1,000,000,000.
Initial stock is 0 to 1000, 1 ≤ k ≤ 1,000,000.
1 ≤ x ≤ 1,000,000,001 (all integers)
Output
one line per query
Example 1 · stdin
4
pear 7 1
fig 7 2
apple 9 3
kiwi 2 4
3
sell fig 2
sell kiwi 5
price apple 7
4
7
3
1
8
stdout
1 apple 7 3
1 apple 7 3
0 kiwi 2 4
4 none
Example 2 · stdin
2
tea 10 5
jam 20 5
2
restock tea 3
price tea 30
3
20
21
31
stdout
0 jam 20 5
1 tea 30 8
2 none
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 1 languages

This problem takes only C++, because it practises returning and taking an element of a vector by reference (Item&) and the C++ standard library's std::sort / std::lower_bound with lambdas (Java, Python and JS always handle objects by reference, so there is nothing to choose; C# has ref returns, but class objects are always references, so they are rarely needed; C has no references and uses pointers).
In Craykon you would put dicts in a list, sort with Sort(compare) and write the binary search yourself.
Four traps: (1) even though findItem returns Item&, receiving it as auto item = findItem(...) makes auto drop the reference and creates a copy.
Neither the sales nor the new price stay in the vector.
Receive it as auto& or Item&.
(2) for (auto item : shelf) std::cin >> item.name ... also reads into copies, so the vector keeps empty items.
A range-for that changes elements uses auto&.
(3) std::sort is not stable, so the order among equal prices is not defined.
The comparison lambda must include the name (std::stable_sort would only give input order, not name order).
(4) lower_bound finds the first element not less than x and upper_bound the first element greater than x, so upper_bound skips an item whose price is exactly x.
The lambda parameters are in a different order too: lower_bound takes (element, value), upper_bound takes (value, element).
Subtracting shelf.begin() from the found iterator gives c, the number of items before it.
Sort after all commands are done, since a price change moves an item.

C++main.cpp · 66 lines
#include <algorithm>#include <iostream>#include <string>#include <vector> struct Item {    std::string name;    int price;    int stock;}; // 이름으로 찾아 vector 안의 원소 그 자체(참조)를 돌려준다. 이름은 반드시 있다Item& findItem(std::vector<Item>& shelf, const std::string& name) {    auto it = std::find_if(shelf.begin(), shelf.end(), [&](const Item& x) { return x.name == name; });    return *it;} // 바꾸는 함수는 Item&를 받는다: 복사본이 아니라 shelf 안의 원소를 바꾼다void update(Item& item, const std::string& op, int k) {    if (op == "sell") {        if (item.stock >= k) item.stock -= k;    } else if (op == "restock") {        item.stock += k;    } else {        item.price = k;    }} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);     int n;    std::cin >> n;    std::vector<Item> shelf(n);    for (auto& item : shelf) std::cin >> item.name >> item.price >> item.stock;  // auto&: 원소에 바로 읽어 넣는다     int m;    std::cin >> m;    for (int i = 0; i < m; i++) {        std::string op, name;        int k;        std::cin >> op >> name >> k;        Item& item = findItem(shelf, name);  // auto&도 된다. auto만 쓰면 참조를 돌려받아도 복사한다        update(item, op, k);    }     // 가격 순, 같으면 이름 순. std::sort는 같은 것끼리의 차례를 지키지 않으니 이름까지 적는다    std::sort(shelf.begin(), shelf.end(), [](const Item& a, const Item& b) {        if (a.price != b.price) return a.price < b.price;        return a.name < b.name;    });     int q;    std::cin >> q;    for (int i = 0; i < q; i++) {        int x;        std::cin >> x;        // 가격이 x 이상인 첫 물건: lower_bound의 비교 함수는 (원소, 찾는 값) 차례로 받는다        auto it = std::lower_bound(shelf.begin(), shelf.end(), x,                                   [](const Item& item, int value) { return item.price < value; });        std::cout << (it - shelf.begin());        if (it == shelf.end()) std::cout << " none\n";        else std::cout << ' ' << it->name << ' ' << it->price << ' ' << it->stock << '\n';    }}