#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxv 1000000000
using namespace std;
struct nod {
int ind, lson, rson, val, lazy;
pii itv;
};
vector <nod> aint;
int ans;
void putlazy (int p) {
if (aint[p].val == aint[p].itv.se - aint[p].itv.fi + 1) return;
aint[p].lazy = 1;
}
void mkson (int p) {
pii it = aint[p].itv; int na, mid = (it.fi + it.se) / 2;
if (aint[p].lson == 0 && it.fi < it.se) {
na = sz(aint); aint[p].lson = na;
aint.pb({na, 0, 0, 0, 0, {it.fi, mid}});
}
if (aint[p].rson == 0 && it.fi < it.se) {
na = sz(aint); aint[p].rson = na;
aint.pb({na, 0, 0, 0, 0, {mid+1, it.se}});
}
}
void update (int p, pii ok) {
pii it = aint[p].itv;
mkson (p);
if (aint[p].lazy == 1) {
if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
}
if (it.fi > ok.se || ok.fi > it.se) return;
if (it.fi >= ok.fi && it.se <= ok.se) {
if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);///!!!
aint[p].val = it.se - it.fi + 1;
return;
}
if (it.fi == it.se) return;
update (aint[p].lson, ok);
update (aint[p].rson, ok);
aint[p].val = aint[aint[p].lson].val + aint[aint[p].rson].val;
}
int q;
void query (int p, pii ok) {
pii it = aint[p].itv;
mkson (p);
if (aint[p].lazy == 1) {
if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
}
if (it.fi > ok.se || ok.fi > it.se) return;
if (it.fi >= ok.fi && it.se <= ok.se) { q += aint[p].val; return; }
if (it.fi == it.se) return;
query (aint[p].lson, ok);
query (aint[p].rson, ok);
}
int prequery (pii ok) {
q = 0;
query (1, ok);
return q;
}
int main () {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin >> t;
aint.pb(nod());
aint.pb({1,0,0,0,0,{1,maxv}});
int a, b, op;
while (t--) {
cin >> op >> a >> b;
if (op == 1) {
ans = prequery ({a+ans,b+ans});
cout << ans << '\n';
}
else update (1, {a+ans, b+ans});
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
30 ms |
7776 KB |
Output is correct |
| 5 |
Correct |
39 ms |
7904 KB |
Output is correct |
| 6 |
Correct |
34 ms |
7892 KB |
Output is correct |
| 7 |
Correct |
38 ms |
7908 KB |
Output is correct |
| 8 |
Correct |
246 ms |
58680 KB |
Output is correct |
| 9 |
Correct |
501 ms |
117224 KB |
Output is correct |
| 10 |
Correct |
512 ms |
117100 KB |
Output is correct |
| 11 |
Correct |
530 ms |
116820 KB |
Output is correct |
| 12 |
Correct |
535 ms |
116720 KB |
Output is correct |
| 13 |
Correct |
611 ms |
232988 KB |
Output is correct |
| 14 |
Correct |
621 ms |
233076 KB |
Output is correct |
| 15 |
Correct |
829 ms |
232056 KB |
Output is correct |
| 16 |
Correct |
827 ms |
231904 KB |
Output is correct |
| 17 |
Correct |
627 ms |
233076 KB |
Output is correct |
| 18 |
Correct |
621 ms |
232960 KB |
Output is correct |
| 19 |
Correct |
834 ms |
231980 KB |
Output is correct |
| 20 |
Correct |
840 ms |
231940 KB |
Output is correct |
