Submission #65280784

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;

#define ll long long
const int MAX = 1000000000;

struct IST
{
  
  int cmin, cmax, mid;
  ll vals[2];
  int tot;
  int lazy;
  IST *l, *r;

  IST(int lo, int hi) {
    cmin = lo;
    cmax = hi;
    mid = (lo + hi) / 2;
    vals[0] = 0;
    vals[1] = 0;
    lazy = 0;
    tot = 0;
    l = NULL;
    r = NULL;
  }

  IST * get_l() {
    if (l == NULL) {
      l = new IST(cmin, mid);
    }
    return l;
  }
  IST * get_r() {
    if (r == NULL) {
      r = new IST(mid + 1, cmax);
    }
    return r;
  }

  void pull() {

    pushdown();

    vals[0] = 0;
    vals[1] = 0;
    tot = 0;

    for (int it = 0; it < 2; it++) {
      if (l != NULL) {
        l->pushdown();
        vals[0] += l->vals[0];
        vals[1] += l->vals[1];
        tot += l->tot;
      }
      swap(l, r);
    }

  }

  void pushdown() {

    if (lazy) {
      swap(vals[0], vals[1]);
      lazy = 0;
      if (cmin != cmax) {
        get_l()->lazy ^= 1;
        get_r()->lazy ^= 1;
      }
    }

  }

  void flip(int minb, int maxb) {

    pushdown();
    if (minb <= cmin && cmax <= maxb) {
      lazy ^= 1;
    }
    else if (cmin > maxb || cmax < minb) {
      return;
    }
    else {
      get_l()->flip(minb, maxb);
      get_r()->flip(minb, maxb);
      pull();
    }

  }

  void add(int c, int parity = 1) {
    pushdown();
    if (cmin == cmax) {
      vals[parity] += c;
      tot++;
      return;
    }

    if (c <= mid) {
      get_l()->add(c, parity);
    }
    else {
      int tl = get_l()->tot & 1;
      get_r()->add(c, parity ^ tl);
    }
    pull();
  }

};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int q; cin >> q;
  IST * root = new IST(0, MAX);

  ll ans = 0;
  while (q--) {

    ll x; cin >> x;

    x += ans;
    x %= MAX;
    x++;

    root->flip(x, MAX);
    root->add(x);
    ans = root->vals[1];
    cout << ans << "\n";

  }
  
}

Submission Info

Judge Result