Submission #548632

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

apple

#include<bits/stdc++.h>
using namespace std;
struct node{
    node* child[2];
    int lazy, sum;
    int tl,tr;
};
node* make_node(int tl,int tr){
    node* temp = new node;
    for(int i = 0;i<2;i++)
	temp->child[i] = NULL;
    temp-> tl = tl;
    temp-> tr = tr;
    temp->lazy = 0;
    temp->sum = 0;
    return temp;
}
node* pull(node *temp){
    temp->sum = temp->child[0]->sum + temp->child[1]->sum;
    temp->lazy = 0;
    return temp;
}
node* push(node* v){
    if(v->lazy == 0 || v->tl == v->tr)return v;    
    int tm = (v->tl + v->tr)/2;
    if(!v->child[0])
	v->child[0] = make_node(v->tl, tm);
    if(!v->child[1])
	v->child[1] = make_node(tm + 1, v->tr);
    v->child[1]->lazy = v->child[0]->lazy = 1;
    v->child[0]->sum = tm - v->tl + 1;
    v->child[1]->sum = v->tr - tm;
    return v;
}
void update(int l,int r,node *v){
    v = push(v);
    if(l > r || !v)
	return;
    else 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;
	if(!v->child[0])
	    v->child[0] = make_node(v->tl, tm);
	if(!v->child[1])
	    v->child[1] = make_node(tm + 1, v->tr);
	update(l, min(tm,r), v->child[0]);
	update(max(l,tm + 1), r, v->child[1]);
	v = pull(v);
    }
}
int query(int l,int r,node* v){
    v = push(v);
    if(l > r || !v)
	return 0;
    else if(l == v->tl && r == v->tr)
	return v->sum;
    else{
	int tm = (v->tl + v->tr)/2;
	if(!v->child[0])
	    v->child[0] = make_node(v->tl, tm);
	if(!v->child[1])
	    v->child[1] = make_node(tm + 1, v->tr);
	return query(l, min(tm, r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    }
}
int main(){
    node* root = make_node(0, 1e9 + 100);
    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);
	}
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	31 ms	8540 KB	Output is correct
5	Correct	36 ms	10292 KB	Output is correct
6	Correct	34 ms	9928 KB	Output is correct
7	Correct	41 ms	10316 KB	Output is correct
8	Correct	246 ms	76832 KB	Output is correct
9	Correct	568 ms	130836 KB	Output is correct
10	Correct	544 ms	146760 KB	Output is correct
11	Correct	606 ms	159400 KB	Output is correct
12	Correct	560 ms	164684 KB	Output is correct
13	Correct	629 ms	205116 KB	Output is correct
14	Correct	586 ms	207168 KB	Output is correct
15	Runtime error	510 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-