Submission #355627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
355627	2021-01-22T21:27:17 Z	AmineTrabelsi	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	507 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	110 ms	50540 KB	Output is correct
5	Correct	48 ms	24428 KB	Output is correct
6	Correct	43 ms	19820 KB	Output is correct
7	Correct	56 ms	25348 KB	Output is correct
8	Correct	478 ms	239212 KB	Output is correct
9	Correct	507 ms	165480 KB	Output is correct
10	Correct	453 ms	146416 KB	Output is correct
11	Runtime error	381 ms	262144 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-