Submission #548639

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548639	2022-04-14T04:54:59 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	605 ms	262144 KB

apple

    #include<bits/stdc++.h>
    using namespace std;
    struct node{
        node* child[2];
        bool lazy;
        int tl,tr,sum;
        node(int l, int r){
    	lazy = 0;
    	sum = 0;
    	tl = l;
    	tr = r;
    	child[0] = child[1] = NULL;
        };
        void add(){
    	int tm = (tl + tr)/2;
    	if(!child[0])
    	   child[0] = new node(tl, tm);
    	if(!child[1])
    	   child[1] = new node(tm + 1, tr);
        }
        int siz(){
    	return tr - tl + 1;
        }
    };
    node *root = new node(1, 1e9);
    void push(node* v){
        if(v->lazy == 0 || v->tl == v->tr)return;
        int tm = (v->tl + v->tr)/2;
        v->add();
        v->child[0]->lazy = 1;
        v->child[1]->lazy = 1;
        v->lazy= 0;
        v->child[0]->sum = v->child[0]->siz();
        v->child[1]->sum = v->child[1]->siz();
    }
    void update(int l,int r,node *v){
        if(l > r || !v)
    	return;
        push(v);
        if(l <= v->tl && r >= v->tr){
    	int siz = v->tr - v->tl + 1;
    	v->lazy = 1;
    	v->sum = siz;
        }
        else{
    	int tm = (v->tl + v->tr)/2;
    	v->add();
    	if(l > tm){
    	    update(l, r, v->child[1]);
    	}
    	else if(r <= tm){
    	    update(l,r, v->child[0]);
    	}
    	else{
    	    update(l, min(tm,r), v->child[0]);
    	    update(max(l,tm + 1), r, v->child[1]);
    	}
    	v->sum = v->child[0]->sum + v->child[1]->sum;
        }
    }
    int query(int l,int r,node* v){
        if(l > r || !v)
    	return 0;
        push(v);
        if(l <= v->tl && r >= v->tr){
    	return v->sum;
        }
        else{
    	int tm = (v->tl + v->tr)/2;
    	v->add();
    	return query(l, min(tm, r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    	if(l > tm){
    	    return query(l, r, v->child[1]);
    	}
    	else if(r <= tm){
    	    return query(l,r, v->child[0]);
    	}
    	else{
    	    return query(l, min(tm,r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    	}
        }
    }
    int main(){
        int q;cin >> q;
        int c = 0;
        while(q--){
    	int d, x, y;cin >> d >> x >> y;
    	x += c;y+=c;
    	if(d == 1){
    	    cout << (c = query(x,y,root)) << "\n";
    	}
    	else{
    	    update(x,y,root);
    	}
        }
    }

Compilation message

apple.cpp: In function 'void push(node*)':
apple.cpp:28:13: warning: unused variable 'tm' [-Wunused-variable]
   28 |         int tm = (v->tl + v->tr)/2;
      |             ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	24 ms	6740 KB	Output is correct
5	Correct	29 ms	8172 KB	Output is correct
6	Correct	29 ms	7792 KB	Output is correct
7	Correct	31 ms	8140 KB	Output is correct
8	Correct	220 ms	61132 KB	Output is correct
9	Correct	440 ms	104612 KB	Output is correct
10	Correct	470 ms	116680 KB	Output is correct
11	Correct	495 ms	126020 KB	Output is correct
12	Correct	486 ms	130168 KB	Output is correct
13	Correct	468 ms	157136 KB	Output is correct
14	Correct	454 ms	158784 KB	Output is correct
15	Runtime error	605 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-