#include "bits/stdc++.h"
using namespace std;
// Hi
struct seg_node {
bool exists; // all trees in range have that thing
seg_node *left, *right;
seg_node() : exists(0),left(NULL),right(NULL){}
};
struct segment_tree{
seg_node *root = new seg_node();
void range_update (int tl,int tr,int l,int r,seg_node* node){
if(tl > r || tr < l)return; // out of range
if(tl >= l && tr <= r){ // totally in
node->exists = 1;
return;
}if(tl == tr)return;
// intersects
push(tl,tr,node);
int mid = (tl+tr)/2;
range_update(tl,mid,l,r,node->left);
range_update(mid+1,tr,l,r,node->right);
}
int range_sum(int tl,int tr,int l,int r,seg_node *node){
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r){
if(node->exists)return tr-tl+1;
}
if(tl == tr)return 0;
int mid = (tl+tr)/2;
push(tl,tr,node);
return range_sum(tl,mid,l,r,node->left)+range_sum(mid+1,tr,l,r,node->right);
}
void push(int tl,int tr,seg_node* node){
if(node->left == NULL)node->left = new seg_node();
if(node->right == NULL)node->right = new seg_node();
if(node->exists){
int mid = (tl+tr)/2;
range_update(tl,mid,tl,mid,node->left);
range_update(mid+1,tr,mid+1,tr,node->right);
}
}
};
const int M = 1e9;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int qq;
cin>>qq;
int c = 0;
segment_tree *Tree = new segment_tree();
while(qq--){
int t,x,y;
cin>>t;
if(t == 1){
cin>>x>>y;
x += c-1;
y += c-1;
int ans = Tree->range_sum(0,M,x,y,Tree->root);
c+= ans;
cout << ans << '\n';
}else{
cin>>x>>y;
x += c-1;
y += c-1;
Tree->range_update(0,M,x,y,Tree->root);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
