# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
136664 | turbat | Monkey and Apple-trees (IZhO12_apple) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define N 1000000000
int m, x, y, c, d, s;
struct segment{
segment *l;
segment *r;
int cnt = 0;
};
void update (segment *seg, int L, int R, int l, int r){
if (seg->cnt == R - L + 1) return;
if (L > r || R < l) return;
if (l <= L && R <= r){
seg->cnt = R - L + 1;
return;
}
int mid = (L + R)/2;
if (!seg->l) seg->l = new segment();
update(seg->l, L, mid, l, r);
if (!seg->r) seg->r = new segment();
update(seg->r, mid + 1, R, l, r);
seg->cnt = seg->l->cnt + seg->r->cnt;
}
int query(segment *seg, int L, int R, int l, int r){
if (L > r || R < l) return 0;
if (l <= L && R <= r) return seg->cnt;
int mid = (L + R)/2, ans = 0;
if (seg->l) ans = query(seg->l, L, mid, l, r);
if (seg->r) ans += query(seg->r, mid + 1, R, l, r);
return ans;
}
int main (){
cin >> m;
while (m--){
cin >> d>> x>> y;
if (d == 2) update(root, 1, N, x + c, y + c);
else {
c = query(root, 1, N, x + c, y + c);
cout << c<< endl;
}
}
}