# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
355628 | AmineTrabelsi | Monkey and Apple-trees (IZhO12_apple) | C++14 | 559 ms | 262148 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
node->exists = 0;
}
}
};
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 |
---|---|---|---|---|
Fetching results... |