#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m;
cin >> m;
int C = 0;
struct Node {
int val, lazy, start, end;
Node *left, *right;
Node() {
val = 0;
lazy = -1;
start = 0, end = (1<<30)-1;
left = right = nullptr;
}
Node(int l, int r) {
val = 0;
lazy = -1;
start = l; end = r;
left = right = nullptr;
}
};
Node root;
auto push_to_sons = [&](Node &v) {
int x = v.lazy;
int mid = (v.start+v.end)/2;
int d = (v.end-v.start+1)/2;
if (v.left == nullptr) v.left = new Node(v.start, mid);
if (v.right == nullptr) v.right = new Node(mid+1, v.end);
if (x == -1) return;
(v.right)->val = x*d;
(v.left)->val = x*d;
(v.right)->lazy = x;
(v.left)->lazy = x;
v.lazy = -1;
};
function<void(int, int, int, Node &)> update = [&](int l, int r, int x, Node &v) {
int a = v.start, b = v.end;
if (r < a || b < l) return;
if (l <= a && b <= r) {
v.val = (b-a+1)*x;
v.lazy = x;
return;
}
push_to_sons(v);
update(l, r, x, *v.left); update(l, r, x, *v.right);
v.val = (v.left)->val+(v.right)->val;
};
function<int(int, int, Node&)> query = [&](int l, int r, Node &v) {
int a = v.start, b = v.end;
if (r < a || b < l) return 0;
if (l <= a && b <= r) {
return v.val;
}
push_to_sons(v);
return query(l, r, *v.left) + query(l, r, *v.right);
};
while (m--) {
int x, l, r;
cin >> x >> l >> r;
l += C; r += C;
if (x == 2) {
update(l, r, 1, root);
}
else {
cout << (C=query(l, r, root)) << '\n';
}
}
function<void(Node &)> clean = [&](Node &v) {
if (v.left == nullptr) {
return;
}
clean(*v.left); clean(*v.right);
delete v.left; delete v.right;
};
clean(root);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
5076 KB |
Output is correct |
5 |
Correct |
16 ms |
6100 KB |
Output is correct |
6 |
Correct |
15 ms |
5844 KB |
Output is correct |
7 |
Correct |
17 ms |
6100 KB |
Output is correct |
8 |
Correct |
134 ms |
45268 KB |
Output is correct |
9 |
Correct |
267 ms |
76896 KB |
Output is correct |
10 |
Correct |
288 ms |
86604 KB |
Output is correct |
11 |
Correct |
316 ms |
93100 KB |
Output is correct |
12 |
Correct |
313 ms |
95820 KB |
Output is correct |
13 |
Correct |
277 ms |
110928 KB |
Output is correct |
14 |
Correct |
279 ms |
111992 KB |
Output is correct |
15 |
Correct |
457 ms |
203480 KB |
Output is correct |
16 |
Correct |
457 ms |
205036 KB |
Output is correct |
17 |
Correct |
292 ms |
115556 KB |
Output is correct |
18 |
Correct |
292 ms |
115848 KB |
Output is correct |
19 |
Correct |
467 ms |
209424 KB |
Output is correct |
20 |
Correct |
472 ms |
209448 KB |
Output is correct |