#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 3e5 + 12;
const int INF = 1e9;
struct node{
node *L, *R;
int sum = 0, tt = 0;
};
void push(node *v, int tl, int tr){
if(!v->tt)
return;
int tm = (tl + tr) / 2;
v->L->sum = tm - tl + 1, v->R->sum = tr - tm;
v->L->tt = v->R->tt = 1, v->tt = 0;
}
void upd(node *v, int tl, int tr, int l, int r){
if(tl > r || l > tr)
return;
if(tl >= l && tr <= r){
v->sum = tr - tl + 1, v->tt = 1;
return;
}
if(!v->L)
v->L = new node();
if(!v->R)
v->R = new node();
push(v, tl, tr);
int tm = (tl + tr) / 2;
upd(v->L, tl, tm, l, r);
upd(v->R, tm + 1, tr, l, r);
v->sum = v->L->sum + v->R->sum;
}
int get(node *v, int tl, int tr, int l, int r){
if(tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return v->sum;
if(!v->L)
v->L = new node();
if(!v->R)
v->R = new node();
push(v, tl, tr);
int tm = (tl + tr) / 2;
return get(v->L, tl, tm, l, r) + get(v->R, tm + 1, tr, l, r);
}
int main () {
// freopen("f.in", "r", stdin);
// freopen("f.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
node *root = new node();
int sums = 0, q;
cin >> q;
for(int tc, l, r;q--;){
cin >> tc >> l >> r, l += sums, r += sums;
if(tc == 1){
int ans = get(root, 1, INF, l, r);
cout << ans << "\n", sums += ans;
}
else{
upd(root, 1, INF, l, r);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
