#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
int sum = 0, lazy = 0;
int l, r;
int left_child = -1, right_child = -1;
Node(int lb, int rb) {
l = lb;
r = rb;
}
};
int n, cnt = 0;
vector<Node> tree;
void extend_left(int curr) {
if(tree[curr].left_child == -1 && tree[curr].l < tree[curr].r) {
int mid = (tree[curr].l+tree[curr].r)/2;
tree[curr].left_child = ++cnt;
tree.push_back(Node(tree[curr].l, mid));
}
}
void extend_right(int curr) {
if(tree[curr].right_child == -1 && tree[curr].l < tree[curr].r) {
int mid = (tree[curr].l+tree[curr].r)/2;
tree[curr].right_child = ++cnt;
tree.push_back(Node(mid+1, tree[curr].r));
}
}
void propagate(int curr) {
if(tree[curr].l == tree[curr].r) return ;
if(tree[curr].lazy == 0) return ;
int mid = (tree[curr].r+tree[curr].l)/2;
tree[tree[curr].left_child].lazy = 1;
tree[tree[curr].left_child].sum = (mid-tree[curr].l+1);
tree[tree[curr].right_child].lazy = 1;
tree[tree[curr].right_child].sum = (tree[curr].r-mid);
tree[curr].lazy = 0;
}
void upd(int l, int r, int curr) {
/*if(curr >= tree.size() || curr < 0) {
while(1) {
}
}*/
if(l <= tree[curr].l && tree[curr].r <= r) {
tree[curr].lazy = 1;
tree[curr].sum = (tree[curr].r-tree[curr].l+1);
return ;
}
if(l > tree[curr].r || r < tree[curr].l) return ;
extend_left(curr);
extend_right(curr);
propagate(curr);
upd(l, r, tree[curr].left_child);
upd(l, r, tree[curr].right_child);
tree[curr].sum = tree[tree[curr].left_child].sum+tree[tree[curr].right_child].sum;
}
int query(int l, int r, int curr) {
/*if(curr >= tree.size() || curr < 0) {
while(1) {
}
}*/
if(l <= tree[curr].l && tree[curr].r <= r) return tree[curr].sum;
if(l > tree[curr].r || r < tree[curr].l) return 0;
extend_left(curr);
extend_right(curr);
propagate(curr);
return query(l, r, tree[curr].left_child) +
query(l, r, tree[curr].right_child);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> q;
tree.reserve(2 * q * __lg(n));
tree.push_back(Node(0, 1e9+1));
int c = 0;
while(q--) {
int flag;
cin >> flag;
if(flag == 1) {
int l, r;
cin >> l >> r;
l += c; r += c;
c = query(l, r, 0);
cout << c << '\n';
}
else {
int l, r;
cin >> l >> r;
l += c; r += c;
upd(l, r, 0);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
