Submission #1138114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138114		Hamed_Ghaffari	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	380 ms	193868 KiB

apple

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define mid (l+r>>1)

const int MX=1<<30;

struct seg {
  int ans;
  bool lz;
  seg *lc, *rc;
  seg(): ans(0), lz(0), lc(NULL), rc(NULL) {}
};

seg *root = new seg();

void pull(seg *v) {
  v->ans = 0;
  if(v->lc) v->ans += v->lc->ans;
  if(v->rc) v->ans += v->rc->ans;
}
void apply(int l, int r, seg *v) {
  v->ans = r-l; v->lz = 1;
}
void push(int l, int r, seg *v) {
  if(r-l==1 || !v->lz) return;
  if(!v->lc) v->lc = new seg();
  if(!v->rc) v->rc = new seg();
  apply(l, mid, v->lc);
  apply(mid, r, v->rc);
  v->lz = 0;
}
void upd(int s, int e, int l=1, int r=MX+1, seg *v=root) {
  push(l, r, v);
  if(s<=l && r<=e) {
    apply(l, r, v);
    return;
  }
  if(s<mid) {
    if(!v->lc) v->lc = new seg();
    upd(s, e, l, mid, v->lc);
  }
  if(e>mid) {
    if(!v->rc) v->rc = new seg();
    upd(s, e, mid, r, v->rc);
  }
  pull(v);
}
int get(int s, int e, int l=1, int r=MX+1, seg *v=root) {
  push(l, r, v);
  if(s<=l && r<=e) return v->ans;
  int res=0;
  if(s<mid && v->lc) res += get(s, e, l, mid, v->lc);
  if(e>mid && v->rc) res += get(s, e, mid, r, v->rc);
  return res;
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  int q;
  cin >> q;
  int c=0;
  while(q--) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c; y += c+1;
    if(d==1) cout << (c=get(x,y)) << '\n';
    else upd(x, y);
  } 
  return 0;
}

• Subtask 1: 100 / 100