Submission #65282181

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
const int MAX_V = 1'000'000'000;
struct Node {
    int num;
    long long s[2];
    int nxt[2];
    Node() {
        num = 0;
        s[0] = s[1] = 0;
        nxt[0] = nxt[1] = 0;
    }
};
vector<Node> seg(1);
void ins(int id, int low, int hi, int x) {
    if (low == hi) {
        seg[id].num ^= 1;
        seg[id].s[seg[id].num ^ 1] += x;
        return;
    }
    int mid = (low + hi) / 2;
    for (int i : {0, 1}) {
        if (!seg[id].nxt[i]) {
            seg[id].nxt[i] = SZ(seg);
            seg.push_back(Node());
        }
    }
    if (x <= mid) {
        ins(seg[id].nxt[0], low, mid, x);
    } else {
        ins(seg[id].nxt[1], mid + 1, hi, x);
    }
    seg[id].num ^= 1;
    for (int i : {0, 1}) {
        seg[id].s[i] = seg[seg[id].nxt[0]].s[i];
    }
    for (int i : {0, 1}) {
        seg[id].s[i] += seg[seg[id].nxt[1]].s[i ^ seg[seg[id].nxt[0]].num];
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int Q;
    cin >> Q;
    long long z = 0;
    while (Q--) {
        int y;
        cin >> y;
        int x = (y + z) % MAX_V + 1;
        ins(0, 1, MAX_V, x);
        z = seg[0].s[0];
        cout << seg[0].s[0] << '\n';
    }
}

Submission Info

Judge Result