oj.uz

Submission #489765

# Submission time Handle Problem Language Result Execution time Memory
489765 2021-11-24T14:18:42 Z czhang2718 Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 282 ms 129840 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){
  push(x, lx, rx);
  if(lx>=l && rx<=r){
    on[x]=1;
    sum[x]=rx-lx;
    return;
  }
  if(lx>=r || rx<=l) return;
  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){
  push(x, lx, rx);
  if(lx>=l && rx<=r) return sum[x];
  if(lx>=r || rx<=l) return 0;
  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 11 ms 3276 KB Output is correct
5 Correct 12 ms 4028 KB Output is correct
6 Correct 12 ms 3932 KB Output is correct
7 Correct 12 ms 4052 KB Output is correct
8 Correct 105 ms 29392 KB Output is correct
9 Correct 233 ms 51156 KB Output is correct
10 Correct 257 ms 57644 KB Output is correct
11 Correct 282 ms 61900 KB Output is correct
12 Correct 235 ms 63732 KB Output is correct
13 Runtime error 236 ms 129840 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -