Submission #65269823

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct N {
    int v, p, sz;
    ll so, se;
    N *l, *r;
    N(int _v) : v(_v), p(rand()), sz(1), so(_v), se(0), l(nullptr), r(nullptr) {}
};
int gsz(N* t) { return t ? t->sz : 0; }
ll gso(N* t) { return t ? t->so : 0; }
ll gse(N* t) { return t ? t->se : 0; }
void upd(N* t) {
    if (!t) return;
    int ls = gsz(t->l);
    ll lso = gso(t->l), lse = gse(t->l);
    bool rootOdd = ((ls + 1) & 1);
    bool flip = ((ls & 1) == 0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct N {
    int v, p, sz;
    ll so, se;
    N *l, *r;
    N(int _v) : v(_v), p(rand()), sz(1), so(_v), se(0), l(nullptr), r(nullptr) {}
};

int gsz(N* t) { return t ? t->sz : 0; }
ll gso(N* t) { return t ? t->so : 0; }
ll gse(N* t) { return t ? t->se : 0; }

void upd(N* t) {
    if (!t) return;
    int ls = gsz(t->l);
    ll lso = gso(t->l), lse = gse(t->l);
    bool rootOdd = ((ls + 1) & 1);
    bool flip = ((ls & 1) == 0);
    ll rso = gso(t->r), rse = gse(t->r);
    ll nso = flip ? rse : rso;
    ll nse = flip ? rso : rse;
    t->sz = 1 + ls + gsz(t->r);
    t->so = lso + (rootOdd ? t->v : 0) + nso;
    t->se = lse + (rootOdd ? 0 : t->v) + nse;
}

void split(N* t, int x, N*& a, N*& b) {
    if (!t) { a = b = nullptr; return; }
    if (t->v < x) {
        split(t->r, x, t->r, b);
        a = t;
    } else {
        split(t->l, x, a, t->l);
        b = t;
    }
    upd(t);
}

N* merge(N* a, N* b) {
    if (!a || !b) return a ? a : b;
    if (a->p > b->p) {
        a->r = merge(a->r, b);
        upd(a);
        return a;
    } else {
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    srand(0);

    int Q;
    cin >> Q;
    N* root = nullptr;
    ll z = 0;

    while (Q--) {
        ll y;
        cin >> y;
        int x = int((y + z) % 1000000000 + 1);

        N *a, *b;
        split(root, x, a, b);
        N* nd = new N(x);
        root = merge(merge(a, nd), b);
        z = root->so;
        cout << z << endl;
    }
    return 0;
}

Submission Info

Judge Result