#include <bits/stdc++.h>
using namespace std;
#define mid ((tl + tr) >> 1)
const int MAXN = 1e5 + 3e4;
struct Node {
int sum = 0;
bool lazy_set = false;
int l = 0, r = 0;
} tree[64 * MAXN];
int ptr = 2;
int newchild() {
return ptr++;
}
void propagate(int tl, int tr, int node) {
if (tree[node].lazy_set) {
tree[node].sum = tr - tl + 1;
if (tl == tr) {
tree[node].lazy_set = false;
return;
}
if (!tree[node].l) tree[node].l = newchild();
if (!tree[node].r) tree[node].r = newchild();
tree[tree[node].l].lazy_set = true;
tree[tree[node].r].lazy_set = true;
}
tree[node].lazy_set = false;
}
void update(int tl, int tr, int node, int l, int r) {
propagate(tl, tr, node);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
tree[node].lazy_set = true;
propagate(tl, tr, node);
return;
}
if (!tree[node].l) tree[node].l = newchild();
if (!tree[node].r) tree[node].r = newchild();
update(tl, mid, tree[node].l, l, r);
update(mid + 1, tr, tree[node].r, l, r);
tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
}
int query(int tl, int tr, int node, int l, int r) {
propagate(tl, tr, node);
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) {
return tree[node].sum;
}
int ret = 0;
if (tree[node].l) ret += query(tl, mid, tree[node].l, l, r);
if (tree[node].r) ret += query(mid + 1, tr, tree[node].r, l, r);
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
for (auto& i : tree) i.l = 0, i.r = 0, i.sum = 0, i.lazy_set = false;
int q;
cin >> q;
int c = 0;
while (q--) {
int t, l, r;
cin >> t >> l >> r;
l += c, r += c;
if (t == 1) cout << (c = query(1, 1'000'000'000, 1, l, r)) << '\n';
else update(1, 1'000'000'000, 1, l, r);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
130648 KB |
Output is correct |
2 |
Correct |
26 ms |
130524 KB |
Output is correct |
3 |
Correct |
25 ms |
130652 KB |
Output is correct |
4 |
Correct |
33 ms |
130516 KB |
Output is correct |
5 |
Correct |
33 ms |
130644 KB |
Output is correct |
6 |
Correct |
34 ms |
130736 KB |
Output is correct |
7 |
Correct |
33 ms |
130568 KB |
Output is correct |
8 |
Correct |
84 ms |
130644 KB |
Output is correct |
9 |
Correct |
159 ms |
130896 KB |
Output is correct |
10 |
Correct |
168 ms |
131044 KB |
Output is correct |
11 |
Correct |
178 ms |
130888 KB |
Output is correct |
12 |
Correct |
164 ms |
131036 KB |
Output is correct |
13 |
Correct |
156 ms |
131156 KB |
Output is correct |
14 |
Correct |
157 ms |
131160 KB |
Output is correct |
15 |
Correct |
203 ms |
131264 KB |
Output is correct |
16 |
Correct |
210 ms |
133456 KB |
Output is correct |
17 |
Correct |
160 ms |
133360 KB |
Output is correct |
18 |
Correct |
163 ms |
133208 KB |
Output is correct |
19 |
Correct |
205 ms |
133200 KB |
Output is correct |
20 |
Correct |
211 ms |
133580 KB |
Output is correct |