#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
#define migmig cin.tie(NULL);ios_base::sync_with_stdio(false)
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define fi first
#define sec second
#define endl "\n"
#define pii pair <int, int>
using namespace std;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll INF18 = 1e18;
const int MAXN = 7e7 + 1;
const int LOG = 23;
int node[MAXN], n = 1e9 + 1, lzy[MAXN], lft[MAXN], rgt[MAXN], now = 1;
ll get(int s, int e, int l = 0, int r = n, int id = 1){
if (s <= l && e >= r) return node[id];
if (s >= r || e <= l) return 0;
int mid = (l + r) / 2;
if (lft[id] == 0) lft[id] = ++now;
if (rgt[id] == 0) rgt[id] = ++now;
if (lzy[id]){
lzy[lft[id]] = 1;
lzy[rgt[id]] = 1;
node[lft[id]] = mid - l;
node[rgt[id]] = r - mid;
}
lzy[id] = 0;
return get(s, e, l, mid, lft[id]) + get(s, e, mid, r, rgt[id]);
}
void upd(int s, int e, int l = 0, int r = n, int id = 1){
if (s <= l && e >= r){
lzy[id] = 1, node[id] = r - l;
return;
}
if (s >= r || e <= l) return;
int mid = (l + r) / 2;
if (lft[id] == 0) lft[id] = ++now;
if (rgt[id] == 0) rgt[id] = ++now;
if (lzy[id]){
lzy[lft[id]] = 1;
lzy[rgt[id]] = 1;
node[lft[id]] = mid - l;
node[rgt[id]] = r - mid;
}
upd(s, e, l, mid, lft[id]);
upd(s, e, mid, r, rgt[id]);
node[id] = node[lft[id]] + node[rgt[id]];
}
void solve(){
int m;
cin >> m;
int c = 0;
for (int i = 0; i < m; i++){
int d, l, r;
cin >> d >> l >> r;
l--;
l += c, r += c;
if (d == 1){
c = get(l, r);
cout << c << endl;
}
else upd(l, r);
}
}
int main(){
migmig;
int tc = 1;
// cin >> tc;
for (int ti = 0; ti < tc; ti++) solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
2140 KB |
Output is correct |
5 |
Correct |
8 ms |
2340 KB |
Output is correct |
6 |
Correct |
8 ms |
2396 KB |
Output is correct |
7 |
Correct |
7 ms |
2512 KB |
Output is correct |
8 |
Correct |
53 ms |
15700 KB |
Output is correct |
9 |
Correct |
111 ms |
27472 KB |
Output is correct |
10 |
Correct |
112 ms |
30144 KB |
Output is correct |
11 |
Correct |
122 ms |
32568 KB |
Output is correct |
12 |
Correct |
116 ms |
33108 KB |
Output is correct |
13 |
Correct |
107 ms |
38540 KB |
Output is correct |
14 |
Correct |
109 ms |
38936 KB |
Output is correct |
15 |
Correct |
163 ms |
69276 KB |
Output is correct |
16 |
Correct |
167 ms |
69964 KB |
Output is correct |
17 |
Correct |
124 ms |
40152 KB |
Output is correct |
18 |
Correct |
109 ms |
40272 KB |
Output is correct |
19 |
Correct |
169 ms |
71184 KB |
Output is correct |
20 |
Correct |
163 ms |
71248 KB |
Output is correct |