#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)
using namespace std;
typedef long long ll;
const int NODE = 1e6 + 2e5;
const int N = 1000000000;
struct node{
int l, r, sum, add;
node(){
l = r = sum = add = 0;
}
} t[NODE];
int c, cnt = 1;
void push(int k, int l, int r){
if(t[k].add){
if(t[k].l==0) t[k].l = ++cnt;
if(t[k].r==0) t[k].r = ++cnt;
t[t[k].l].add = 1;
t[t[k].r].add = 1;
t[k].sum = (r - l + 1);
t[k].add = 0;
}
}
void up(int k, int l, int r, int u, int v){
push(k, l, r);
if(r < u || l > v) return ;
if(l >= u && r <= v){
t[k].add = 1;
t[k].sum = (r - l + 1);
return ;
}
int m = (l + r)/2;
if(t[k].l==0) t[k].l = ++cnt;
if(t[k].r==0) t[k].r = ++cnt;
up(t[k].l, l, m, u, v);
up(t[k].r, m + 1, r, u, v);
t[k].sum = t[t[k].l].sum + t[t[k].r].sum;
}
int get1(int k, int l, int r, int u, int v){
push(k, l, r);
if(r < u || l > v) return 0;
if(l >= u && r <= v) return t[k].sum;
int m = (l + r)/2;
int res = 0;
if(t[k].l){ /// neu khong co t[k].l thi nghia la no chua duoc update(de len tao chin do) lan nao ca => res = 0 khong can suy nghi, vi
/// lam the moi tiet kiem duoc bo nho
res += (get1(t[k].l, l, m, u, v));
}
if(t[k].r){
res += get1(t[k].r, m + 1, r, u, v);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
int m; cin >> m;
while(m--){
int ty, u, v; cin >> ty >> u >> v;
u += c, v += c;
if(ty==1){
int x = c;
c = x + get1(1, 1, N, u, v);
cout << c - x << endl;
}
else up(1, 1, N, u, v);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19192 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
