2025 S5 - To-do List

1// By Daniel Zhang, Pinetree Secondary
2
3// Idea - maintain a segment tree where each node stores the latest time possible to complete all the tasks
4// in as little time as possible, which is the sum of the times of the tasks
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10typedef long long ll;
11
12struct Node {
13    ll begin, time;
14};
15
16const ll MAXN = 1000025;
17Node tree[4*MAXN];
18ll arr[MAXN];
19vector<pair<ll, ll>> hw;
20
21Node recalculate(ll node) {
22    Node l = tree[2 * node + 1], r = tree[2 * node + 2];
23    if(l.begin == INT_MAX) return r;  // left is empty
24    if(r.begin == INT_MAX) return l;  // right is empty
25
26    return {max(l.begin + l.time, r.begin) - l.time, l.time + r.time};
27}
28
29
30void update(ll node, ll left, ll right, ll index, ll value) {
31    if (left == right) {
32        if (value == 0) {
33            tree[node] = {INT_MAX, INT_MIN};
34        }
35        else tree[node] = {index, value};
36    }
37    else {
38        ll middle = (left + right) / 2;
39        if (index <= middle) update(node * 2 + 1, left, middle, index, value); // update left branch
40        else update(node * 2 + 2, middle + 1, right, index, value);
41        tree[node] = recalculate(node);
42    }
43}
44
45ll ans = 0;
46const ll mod = 1e6 + 3;
47
48signed main() {
49    ios::sync_with_stdio(0); cin.tie(0);
50
51    ll q; cin >> q;
52
53    for (ll i=0; i<4*MAXN; i++) tree[i] = {INT_MAX, INT_MIN};
54
55    for (ll i=0; i<q; i++) {
56        char command; cin >> command;
57        if (command == 'A') {
58            ll s, t; cin >> s >> t; 
59            s = (s + ans - 1 + mod) % mod; t = (t + ans) % mod;
60            arr[s] += t;
61            update(0, 0, MAXN, s, arr[s]);
62            hw.push_back({s, t});
63        }
64
65        else {
66            ll idx; cin >> idx; 
67            idx = (idx + ans - 1) % mod;
68            ll s = hw[idx].first;
69            ll t = hw[idx].second;
70            arr[s] -= t;
71            update(0, 0, MAXN, s, arr[s]);
72        }
73
74        ans = tree[0].begin + tree[0].time;
75        cout << ans << "\n";
76    }
77}
78
79