## Intuition The problem involves a large number of cells, but Freda can only reach specific cells based on her step size `k`. The challenge is to efficiently manage and query the treasure values in these reachable cells, especially given the constraints on the number of operations and the size of `h`. ## Approach 1. **Data Structures**: Use a map to store the treasure cells and their values. This allows efficient updates and queries. 2. **Reachable Cells Calculation**: For any given `k`, Freda can reach cells of the form `1 + i*k` where `i` is a non-negative integer. We need to efficiently determine which treasure cells are reachable for any given `k`. 3. **Operations Handling**: - **Type 1 (Change k)**: Update the step size `k`. Recalculate the set of reachable treasure cells. - **Type 2 (Decrease Treasure Value)**: Decrease the value of a specific treasure cell. Ensure the value remains positive. - **Type 3 (Query Maximum Treasure Value)**: Find the maximum treasure value among the reachable treasure cells. 4. **Efficiency Considerations**: Given the constraints, particularly the large value of `h`, we focus on the number of operations (`m`) and the number of treasure cells (`n`). The map data structure allows us to efficiently handle updates and queries. ## Complexity - **Time**: O(n + m * log n) where `n` is the number of treasure cells and `m` is the number of operations. The log factor comes from map operations. - **Space**: O(n) for storing treasure cells and their values. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long h; int n, m, k; cin >> h >> n >> m >> k; map treasures; for (int i = 0; i < n; ++i) { long long a; int c; cin >> a >> c; treasures[a] = c; } set reachable; auto updateReachable = [&]() { reachable.clear(); for (long long i = 1; i <= h; i += k) { if (treasures.count(i)) { reachable.insert(i); } } }; updateReachable(); for (int i = 0; i < m; ++i) { int type; cin >> type; if (type == 1) { cin >> k; updateReachable(); } else if (type == 2) { int x, y; cin >> x >> y; auto it = treasures.begin(); advance(it, x - 1); it->second -= y; } else if (type == 3) { int maxTreasure = 0; for (auto cell : reachable) { maxTreasure = max(maxTreasure, treasures[cell]); } cout << maxTreasure << '\n'; } } return 0; } ``` This solution efficiently handles the operations by recalculating reachable cells only when `k` changes and using a map to manage treasure values. The use of a set for reachable cells ensures that we only consider valid treasure cells during queries.

Fetch the Treasure

Problem Details