#include <bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}
struct Node{
int lson, rson;
int sum;
int settag;
Node(){
lson = rson = -1;
sum = 1;
settag = -1;
}
} st[64*100100];
int nodecnt = 1;
void pushdown(int node, int l, int mid, int r){
if (st[node].lson == -1)
st[node].lson = ++nodecnt;
if (st[node].rson == -1)
st[node].rson = ++nodecnt;
if (st[node].settag == -1)
return;
st[st[node].lson].sum = (mid-l+1)*st[node].settag;
st[st[node].rson].sum = (r-mid)*st[node].settag;
st[st[node].lson].settag = st[st[node].rson].settag = st[node].settag;
st[node].settag = -1;
}
void U(int node, int l, int r, int tl, int tr, int val){
if (l > tr || r < tl)
return;
if (l >= tl && r <= tr){
st[node].sum = (r-l+1)*val;
st[node].settag = val;
return;
}
int mid = (l+r)/2;
pushdown(node, l, mid, r);
U(st[node].lson, l, mid, tl, tr, val);
U(st[node].rson, mid+1, r, tl, tr, val);
st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}
int S(int node, int l, int r, int tl, int tr){
if (l > tr || r < tl)
return 0;
if (l >= tl && r <= tr){
return st[node].sum;
}
int mid = (l+r)/2;
pushdown(node, l, mid, r);
return S(st[node].lson, l, mid, tl, tr)+S(st[node].rson, mid+1, r, tl, tr);
}
int main(){
fastIO();
int Q; cin >> Q;
int C = 0;
U(1, 1, 1000000000, 1, 1000000000, 1);
while (Q--){
int k; cin >> k;
int a, b; cin >> a >> b;
if (k == 1){
int val = (b+C-(a+C)+1)-S(1, 1, 1000000000, a+C, b+C);
cout << val << "\n";
C += val;
} else {
U(1, 1, 1000000000, a+C, b+C, 0);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
100548 KB |
Output is correct |
| 2 |
Incorrect |
58 ms |
100528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
