Submission #148145

#	Time	Username	Problem	Language	Result	Execution time	Memory
148145		catalystgma	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	840 ms	233076 KiB

apple

#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxv 1000000000

using namespace std;

struct nod {
  int ind, lson, rson, val, lazy;
  pii itv;
};

vector <nod> aint;
int ans;

void putlazy (int p) {
  if (aint[p].val == aint[p].itv.se - aint[p].itv.fi + 1) return;
  aint[p].lazy = 1;
}

void mkson (int p) {
  pii it = aint[p].itv; int na, mid = (it.fi + it.se) / 2;
  if (aint[p].lson == 0 && it.fi < it.se) {
    na = sz(aint); aint[p].lson = na;
    aint.pb({na, 0, 0, 0, 0, {it.fi, mid}});
  }
  if (aint[p].rson == 0 && it.fi < it.se) {
    na = sz(aint); aint[p].rson = na;
    aint.pb({na, 0, 0, 0, 0, {mid+1, it.se}});
  }
}

void update (int p, pii ok) {
  pii it = aint[p].itv;
  mkson (p);
  if (aint[p].lazy == 1) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
    aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
  }
  if (it.fi > ok.se || ok.fi > it.se) return;
  if (it.fi >= ok.fi && it.se <= ok.se) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);///!!!
    aint[p].val = it.se - it.fi + 1;
    return;
  }
  if (it.fi == it.se) return;
  update (aint[p].lson, ok);
  update (aint[p].rson, ok);
  aint[p].val = aint[aint[p].lson].val + aint[aint[p].rson].val;
}

int q;
void query (int p, pii ok) {
  pii it = aint[p].itv;
  mkson (p);
  if (aint[p].lazy == 1) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
    aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
  }
  if (it.fi > ok.se || ok.fi > it.se) return;
  if (it.fi >= ok.fi && it.se <= ok.se) { q += aint[p].val; return; }
  if (it.fi == it.se) return;
  query (aint[p].lson, ok);
  query (aint[p].rson, ok);
}

int prequery (pii ok) {
  q = 0;
  query (1, ok);
  return q;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int t; cin >> t;
  aint.pb(nod());
  aint.pb({1,0,0,0,0,{1,maxv}});
  int a, b, op;
  while (t--) {
    cin >> op >> a >> b;
    if (op == 1) {
      ans = prequery ({a+ans,b+ans});
      cout << ans << '\n';
    }
    else update (1, {a+ans, b+ans});
  }
  return 0;
}

• Subtask 1: 100 / 100