Submission #489767

#	Time	Username	Problem	Language	Result	Execution time	Memory
489767		czhang2718	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	218 ms	71156 KiB

apple

#include "bits/stdc++.h"
using namespace std;

int m;
const int MX=7000000;
int cnt;
int child[MX][2];
int on[MX], sum[MX];

void push(int x, int lx, int rx){
  if(!on[x]) return;
  if(!child[x][0]) child[x][0]=++cnt, child[x][1]=++cnt;
  on[child[x][0]]=on[child[x][1]]=1;
  int m=(lx+rx)/2;
  sum[child[x][0]]=m-lx;
  sum[child[x][1]]=rx-m;
}

void upd(int l, int r, int x, int lx, int rx){
  if(lx>=l && rx<=r){
    on[x]=1;
    sum[x]=rx-lx;
    return;
  }
  if(lx>=r || rx<=l) return;
  push(x, lx, rx);
  int m=(lx+rx)/2;
  if(!child[x][0]) child[x][0]=++cnt, child[x][1]=++cnt;
  upd(l, r, child[x][0], lx, m);
  upd(l, r, child[x][1], m, rx);
  sum[x]=sum[child[x][0]]+sum[child[x][1]];
}

void upd(int l, int r){
  upd(l, r, 0, 0, 1e9+1);
}

int calc(int l, int r, int x, int lx, int rx){
  if(lx>=l && rx<=r) return sum[x];
  if(lx>=r || rx<=l) return 0;
  push(x, lx, rx);
  int m=(lx+rx)/2;
  if(!child[x][0]) child[x][0]=++cnt, child[x][1]=++cnt;
  return calc(l, r, child[x][0], lx, m)+calc(l, r, child[x][1], m, rx);
}

int calc(int l, int r){
  return calc(l, r, 0, 0, 1e9+1);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> m;
  int c=0;
  while(m--){
    int op, x, y; cin >> op >> x >> y;
    x+=c;
    y+=c;
    if(op==1){
      int ans=calc(x, y+1);
      cout << ans << '\n';
      c=ans;
    }
    else upd(x, y+1);
  }
}

• Subtask 1: 100 / 100