oj.uz

Submission #489764

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

int m;
const int MX=2000000;
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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 11 ms 3532 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 12 ms 4020 KB Output is correct
7 Correct 12 ms 4172 KB Output is correct
8 Correct 106 ms 30116 KB Output is correct
9 Runtime error 152 ms 65148 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -