#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e9;
const ll linf = 1e18;
int st[20 * N], lc[20 * N], rc[20 * N], lzy[20 * N], tsz, root;
void Propagate(int c, int l, int r) {
if (lzy[c] == 0) return;
if (l < r) {
if (!lc[c]) lc[c] = ++tsz;
lzy[lc[c]] = lzy[c];
if (!rc[c]) rc[c] = ++tsz;
lzy[rc[c]] = lzy[c];
}
st[c] = r - l + 1;
lzy[c] = 0;
}
void Set(int &c, int l, int r, int ql, int qr) {
if (!c) c = ++tsz;
Propagate(c, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lzy[c] = 1;
Propagate(c, l, r);
return;
}
int mid = l + r >> 1;
Set(lc[c], l, mid, ql, qr);
Set(rc[c], mid + 1, r, ql, qr);
st[c] = st[lc[c]] + st[rc[c]];
}
int Get(int &c, int l, int r, int ql, int qr) {
if (!c) c = ++tsz;
Propagate(c, l, r);
if (r < ql || qr < l) return 0;
if (ql <= l && r <= qr) return st[c];
int mid = l + r >> 1;
return Get(lc[c], l, mid, ql, qr) + Get(rc[c], mid + 1, r, ql, qr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q; cin >> q;
ll C = 0;
while (q--) {
int t;
ll xx, yy;
cin >> t >> xx >> yy;
int x = xx + C; int y = yy + C;
if (t == 1) {
int k = Get(root, 1, M, x, y);
cout << k << en;
C += k;
}
else Set(root, 1, M, x, y);
}
return 0;
}
Compilation message
apple.cpp: In function 'void Set(int&, int, int, int, int)':
apple.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid = l + r >> 1;
| ~~^~~
apple.cpp: In function 'int Get(int&, int, int, int, int)':
apple.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
