#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int sum;
bool lz;
node* c[2];
node() {
sum = 0;
lz = false;
c[0] = c[1] = NULL;
}
void push(int l, int mid, int r) {
if (lz) {
c[0]->sum = mid-l+1;
c[1]->sum = r-mid;
c[0]->lz = c[1]->lz = true;
lz = false;
}
}
void upd(int a, int b, int l=0, int r=1e9-1) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
sum = r-l+1;
lz = true;
} else {
int mid = (l+r)/2;
if (!c[0]) c[0] = new node();
if (!c[1]) c[1] = new node();
push(l, mid, r);
c[0]->upd(a, b, l, mid);
c[1]->upd(a, b, mid+1, r);
sum = c[0]->sum + c[1]->sum;
}
}
int qry(int a, int b, int l=0, int r=1e9-1) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return sum;
int mid = (l+r)/2;
if (!c[0]) c[0] = new node();
if (!c[1]) c[1] = new node();
push(l, mid, r);
return c[0]->qry(a, b, l, mid) + c[1]->qry(a, b, mid+1, r);
}
};
ll m, c;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
node root = node();
cin >> m;
for (ll i=0, d, x, y; i<m; ++i) {
cin >> d >> x >> y;
if (d == 1) {
int cnt = root.qry(x+c-1, y+c-1);
c += cnt;
cout << cnt << '\n';
} else {
root.upd(x+c-1, y+c-1);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
