#include <bits/stdc++.h>
using namespace std;
struct node {
int sum = 0;
int l = -1;
int r = -1;
int tl,tr;
bool has = false;
};
const int MAX_N = 2500000;
const int MAX_V = 1e9;
int cnt = 0;
node segt[4*MAX_N+1];
void timeout(){
if (cnt >= 4*MAX_N+1){
while (true){
cnt += 1;
}
}
}
void upd(int idx, int tl, int tr){
if (segt[idx].tl > tr || segt[idx].tr < tl){
return;
}
if (segt[idx].tl >= tl && segt[idx].tr <= tr){
segt[idx].has = true;
segt[idx].sum = segt[idx].tr - segt[idx].tl + 1;
return;
}
int mid = (segt[idx].tl + segt[idx].tr)/2;
if (segt[idx].l == -1){
segt[idx].l = cnt;
cnt ++;
timeout();
segt[segt[idx].l].tl = segt[idx].tl;
segt[segt[idx].l].tr = mid;
}
if (segt[idx].r == -1){
segt[idx].r = cnt;
cnt ++;
timeout();
segt[segt[idx].r].tl = mid+1;
segt[segt[idx].r].tr = segt[idx].tr;
}
upd(segt[idx].l,tl,tr);
upd(segt[idx].r,tl,tr);
//setting sum
int cl = segt[idx].l;
int cr = segt[idx].r;
if (segt[idx].has){
segt[idx].sum = segt[idx].tr - segt[idx].tl +1;
return;
}
segt[idx].sum = segt[cl].sum + segt[cr].sum;
return;
}
int query(int idx, int tl, int tr, bool chas){
if (segt[idx].tl > tr || segt[idx].tr < tl){
return 0;
}
if (segt[idx].has){
chas = true;
}
if (segt[idx].tl >= tl && segt[idx].tr <= tr){
// cout << idx << ": " << segt[idx].tl << ' ' << segt[idx].tr <<" " << segt[idx].sum << " asd " << tl << ", " << tr << " " << (int) chas << '\n';
if (chas){
return segt[idx].tr - segt[idx].tl + 1;
}
return segt[idx].sum;
}
int mid = (segt[idx].tr + segt[idx].tl)/2;
if (segt[idx].l == -1){
segt[idx].l = cnt;
cnt ++;
timeout();
segt[segt[idx].l].tl = segt[idx].tl;
segt[segt[idx].l].tr = mid;
}
if (segt[idx].r == -1){
segt[idx].r = cnt;
cnt ++;
timeout();
segt[segt[idx].r].tl = mid+1;
segt[segt[idx].r].tr = segt[idx].tr;
}
return query(segt[idx].l,tl,tr,chas)+query(segt[idx].r,tl,tr,chas);
}
int main()
{
int m;
cin >> m;
int d,x,y;
segt[0].tl = 1;
segt[0].tr = MAX_V;
cnt ++;
int c = 0;
int res;
for (int i =0; i < m; i++){
cin >> d >> x >> y;
if (d == 1){
// cout << c << ": ";
res = query(0,x+c,y+c,false);
c += res;
cout << res << '\n';
} else {
upd(0,x+c,y+c);
}
}
//cout << MAX_V << " " << MAX_N << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
235016 KB |
Output is correct |
| 2 |
Incorrect |
88 ms |
235012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
