oj.uz

Submission #489766

# Submission time Handle Problem Language Result Execution time Memory
489766 2021-11-24T14:21:51 Z czhang2718 Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 243 ms 129996 KB 
#include "bits/stdc++.h"
using namespace std;

int m;
const int MX=4000000;
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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 8 ms 1868 KB Output is correct
5 Correct 10 ms 2184 KB Output is correct
6 Correct 9 ms 2124 KB Output is correct
7 Correct 9 ms 2124 KB Output is correct
8 Correct 66 ms 14788 KB Output is correct
9 Correct 161 ms 25584 KB Output is correct
10 Correct 163 ms 28320 KB Output is correct
11 Correct 186 ms 30452 KB Output is correct
12 Correct 179 ms 31328 KB Output is correct
13 Correct 136 ms 36568 KB Output is correct
14 Correct 137 ms 38908 KB Output is correct
15 Runtime error 243 ms 129996 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -