#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
struct node{
int sum,lazy,l,r,tl,tr;
node(): sum(0), lazy(0), l(0), r(0), tl(1), tr(1e9) {};
};
struct SegTree{
vector<node> seg;
SegTree(){
seg.pb(node());
};
void push(int v,int tl,int tr){
int tm = (tl + tr) / 2;
if(seg[v].l == 0){
seg[v].l = seg.size();
seg.pb(node());
seg[seg[v].l].tl = tl;
seg[seg[v].l].tr = tm;
}
if(seg[v].r == 0){
seg[v].r = seg.size();
seg.pb(node());
seg[seg[v].r].tl = tm + 1;
seg[seg[v].r].tr = tr;
}
assert(seg[v].r < seg.size());
if(!seg[v].lazy) return;
seg[seg[v].r].lazy = seg[v].lazy;
seg[seg[v].r].sum = seg[v].lazy * (tr - tm);
seg[seg[v].l].lazy = seg[v].lazy;
seg[seg[v].l].sum = seg[v].lazy * (tm - tl + 1);
seg[v].lazy = 0;
}
void upd(int v,int l,int r,int tl,int tr,int x){
if(tl > r || tr < l) return;
if(tl >= l && tr <= r){
seg[v].sum = (tr - tl + 1) * x;
seg[v].lazy = x;
return;
};
push(v,tl,tr);
int tm = (tl + tr) / 2;
upd(seg[v].l,l,r,tl,tm,x), upd(seg[v].r,l,r,tm+1,tr,x);
seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}
int get(int v,int tl,int tr,int l,int r){
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r){
return seg[v].sum;
}
push(v,tl,tr);
int tm = (tl + tr) / 2;
return get(seg[v].l,tl,tm,l,r) + get(seg[v].r,tm+1,tr,l,r);
}
int get(int l,int r){
return get(0,1,1e9,l,r);
}
};
void solve(){
SegTree seg;
int q,c = 0; cin >> q;
for(int i = 0; i < q; i++){
int ty,l,r; cin >> ty >> l >> r;
if(ty == 2){
seg.upd(0,l + c,r + c,1,1e9,1);
}
else{
int res = seg.get(l+c,r+c);
cout << res << endl; c = res;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from apple.cpp:1:
apple.cpp: In member function 'void SegTree::push(int, int, int)':
apple.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | assert(seg[v].r < seg.size());
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
11 ms |
3492 KB |
Output is correct |
5 |
Correct |
13 ms |
3516 KB |
Output is correct |
6 |
Correct |
15 ms |
3528 KB |
Output is correct |
7 |
Correct |
14 ms |
3536 KB |
Output is correct |
8 |
Correct |
96 ms |
25088 KB |
Output is correct |
9 |
Correct |
202 ms |
49792 KB |
Output is correct |
10 |
Correct |
214 ms |
49884 KB |
Output is correct |
11 |
Correct |
209 ms |
49840 KB |
Output is correct |
12 |
Correct |
211 ms |
49808 KB |
Output is correct |
13 |
Correct |
221 ms |
99392 KB |
Output is correct |
14 |
Correct |
218 ms |
99268 KB |
Output is correct |
15 |
Correct |
338 ms |
200024 KB |
Output is correct |
16 |
Correct |
340 ms |
200096 KB |
Output is correct |
17 |
Correct |
219 ms |
101400 KB |
Output is correct |
18 |
Correct |
222 ms |
101380 KB |
Output is correct |
19 |
Correct |
339 ms |
200076 KB |
Output is correct |
20 |
Correct |
343 ms |
200168 KB |
Output is correct |