Submission #352237

#	Time	Username	Problem	Language	Result	Execution time	Memory
352237		AmineTrabelsi	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	384 KiB

apple

#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;
}

• Subtask 1: 0 / 100