#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005
#define M 80*N
int ALLOC = 1, A[M], L[M], R[M];
int sparse0() { return ALLOC++; }
void push(int v, int l, int r)
{
if (!L[v] && l != r)
{
int m = (l+r)/2;
L[v] = sparse0();
R[v] = sparse0();
}
if (A[v] == r-l+1)
{
if (l != r)
{
int m = (l+r)/2;
A[L[v]] = m-l+1, A[R[v]] = r-m;
}
}
}
void ripe(int v, int l, int r, int x, int y)
{
push(v, l,r );
if (r < x || y < l) return;
if (x <= l && r <= y) { A[v] = r-l+1; push(v, l, r); return; }
int m = (l+r)/2;
ripe(L[v], l, m, x, y), ripe(R[v], m+1, r, x, y); A[v] = A[L[v]] + A[R[v]];
}
int query(int v, int l, int r,int x, int y)
{
push(v, l, r);
if (r < x || y < l) return 0;
if (x <= l && r <= y) return A[v];
return query(L[v], l, (l+r)/2, x, y) + query(R[v], (l+r)/2+1, r, x, y);
}
int main()
{
++ALLOC;
ShinLena;
int m = 1, d, x, y, c = 0;
for (cin >> m; m--;)
{
cin >> d >> x >> y;
if (d == 1) cout << (c = query(1, 1, 1e9, x+c, y+c)) << '\n';
else ripe(1, 1, 1e9, x+c, y+c);
}
return 0;
}
Compilation message
apple.cpp: In function 'void push(int, int, int)':
apple.cpp:25:13: warning: unused variable 'm' [-Wunused-variable]
25 | int m = (l+r)/2;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
408 KB |
Output is correct |
4 |
Correct |
8 ms |
5432 KB |
Output is correct |
5 |
Correct |
11 ms |
5724 KB |
Output is correct |
6 |
Correct |
11 ms |
5600 KB |
Output is correct |
7 |
Correct |
12 ms |
5720 KB |
Output is correct |
8 |
Correct |
68 ms |
23636 KB |
Output is correct |
9 |
Correct |
160 ms |
36432 KB |
Output is correct |
10 |
Correct |
171 ms |
37692 KB |
Output is correct |
11 |
Correct |
173 ms |
43048 KB |
Output is correct |
12 |
Correct |
179 ms |
43376 KB |
Output is correct |
13 |
Correct |
172 ms |
54952 KB |
Output is correct |
14 |
Correct |
155 ms |
55180 KB |
Output is correct |
15 |
Correct |
220 ms |
98132 KB |
Output is correct |
16 |
Correct |
219 ms |
98456 KB |
Output is correct |
17 |
Correct |
157 ms |
55860 KB |
Output is correct |
18 |
Correct |
171 ms |
55884 KB |
Output is correct |
19 |
Correct |
218 ms |
99288 KB |
Output is correct |
20 |
Correct |
235 ms |
99132 KB |
Output is correct |