#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 100001;
const ll VMAX = 10000001;
const ll INF = (1LL << 55);
const ll MOD = 1000007;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;
struct node {
int l, r;
int sum;
int lazy;
void init() {
l = r = -1;
lazy = sum = 0;
}
} aint[NMAX * 20];
int nodes;
void propaga(int node, int st, int dr) {
if(aint[node].lazy == 0)
return;
if(st != dr) {
if(aint[node].l == -1) {
aint[node].l = ++nodes;
aint[nodes].init();
}
if(aint[node].r == -1) {
aint[node].r = ++nodes;
aint[nodes].init();
}
aint[aint[node].l].lazy = aint[aint[node].r].lazy = 1;
}
aint[node].lazy = 0;
aint[node].sum = (dr - st + 1);
}
void update(int node, int st, int dr, int l, int r) {
if(aint[node].sum == dr - st + 1){
return;
}
propaga(node, st, dr);
if(l <= st && dr <= r) {
aint[node].lazy = 1;
return;
}
int mid = (st + dr) / 2;
if(aint[node].l == -1) {
aint[node].l = ++nodes;
aint[nodes].init();
}
if(aint[node].r == -1) {
aint[node].r = ++nodes;
aint[nodes].init();
}
if(l <= mid) {
update(aint[node].l, st, mid, l, r);
}
if(r > mid) {
update(aint[node].r, mid + 1, dr, l, r);
}
propaga(aint[node].l, st, mid);
propaga(aint[node].r, mid + 1, dr);
aint[node].sum = aint[aint[node].l].sum + aint[aint[node].r].sum;
}
int query(int node, int st, int dr, int l, int r) {
propaga(node, st, dr);
if(aint[node].sum == dr - st + 1) return aint[node].sum;
if(aint[node].sum == 0) return 0;
if(l <= st && dr <= r) {
return aint[node].sum;
}
int mid = (st + dr) / 2;
if(aint[node].l == -1) {
aint[node].l = ++nodes;
aint[nodes].init();
}
if(aint[node].r == -1) {
aint[node].r = ++nodes;
aint[nodes].init();
}
int sol = 0;
if(l <= mid) {
sol += query(aint[node].l, st, mid, l, r);
}
if(r > mid) {
sol += query(aint[node].r, mid + 1, dr, l, r);
}
return sol;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
nodes = 1;
aint[nodes].init();
int q;
cin >> q;
int ans = 0;
while(q--){
int a, b, c;
cin >> a >> b >> c;
b += ans;
c += ans;
if(a == 2){
update(1, 1, VMAX, b, c);
}else{
ans = query(1, 1, VMAX, b, c);
cout << ans << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
