#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
const int INF = 1e18, MOD = 1e9 + 7, N = 1e9 + 1;
void setIO(string name = ""){
ios::sync_with_stdio(false);
cin.tie(0);
}
template<class T> struct seg{
T val, lz;
seg<T> *lc, *rc;
int sz;
seg(int n) : sz(n){val = lz = 0; lc = rc = NULL;}
void pull(){
val = (lc ? lc -> val : 0) + (rc ? rc -> val : 0);
}
void push(int l, int r){
int m = l + r >> 1;
if(!lc)lc = new seg(m - l);
if(!rc)rc = new seg(r - m);
if(!lz)return;
lc -> val = lc -> sz;
lc -> lz = 1;
rc -> val = rc -> sz;
rc -> lz = 1;
lz = 0;
}
void add(int a, int b, T v, int l, int r){
if(a <= l && b >= r){
val = r - l, lz = 1;
return;
}
push(l, r);
int m = l + r >> 1;
if(a < m){
lc -> add(a, b, v, l, m);
}
if(b > m){
rc -> add(a, b, v, m, r);
}
pull();
}
T query(int a, int b, int l, int r){
if(a <= l && b >= r)return val;
push(l, r);
int m = l + r >> 1, ans = 0;
if(a < m)ans += lc -> query(a, b, l, m);
if(b > m)ans += rc -> query(a, b, m, r);
return ans;
}
void add(int a, int b, T v){add(a, b, v, 0, sz);}
T query(int a, int b){return query(a, b, 0, sz);}
};
signed main(){
setIO();
seg<int> rt(N);
int n, c = 0;
cin >> n;
while(n--){
int t, l, r;
cin >> t >> l >> r;
l = l - 1 + c, r = r + c;
if(t == 1){
c = rt.query(l, r);
cout << c << '\n';
}else{
rt.add(l, r, 1);
}
}
}
Compilation message
apple.cpp: In instantiation of 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]':
apple.cpp:56:39: required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30: required from here
apple.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int m = l + r >> 1, ans = 0;
| ~~^~~
apple.cpp: In instantiation of 'void seg<T>::add(long long int, long long int, T, long long int, long long int) [with T = long long int]':
apple.cpp:55:36: required from 'void seg<T>::add(long long int, long long int, T) [with T = long long int]'
apple.cpp:72:27: required from here
apple.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m = l + r >> 1;
| ~~^~~
apple.cpp: In instantiation of 'void seg<T>::push(long long int, long long int) [with T = long long int]':
apple.cpp:49:9: required from 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]'
apple.cpp:56:39: required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30: required from here
apple.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
14 ms |
4812 KB |
Output is correct |
| 5 |
Correct |
17 ms |
5776 KB |
Output is correct |
| 6 |
Correct |
20 ms |
5652 KB |
Output is correct |
| 7 |
Correct |
17 ms |
5788 KB |
Output is correct |
| 8 |
Correct |
133 ms |
43704 KB |
Output is correct |
| 9 |
Correct |
274 ms |
75532 KB |
Output is correct |
| 10 |
Correct |
287 ms |
83564 KB |
Output is correct |
| 11 |
Correct |
287 ms |
90012 KB |
Output is correct |
| 12 |
Correct |
288 ms |
92692 KB |
Output is correct |
| 13 |
Correct |
269 ms |
108736 KB |
Output is correct |
| 14 |
Correct |
278 ms |
109756 KB |
Output is correct |
| 15 |
Correct |
434 ms |
200392 KB |
Output is correct |
| 16 |
Correct |
446 ms |
201788 KB |
Output is correct |
| 17 |
Correct |
288 ms |
113480 KB |
Output is correct |
| 18 |
Correct |
273 ms |
113508 KB |
Output is correct |
| 19 |
Correct |
438 ms |
206148 KB |
Output is correct |
| 20 |
Correct |
441 ms |
206248 KB |
Output is correct |
