Submission #548631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548631	2022-04-14T04:24:10 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	584 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)
	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)
	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	1 ms	212 KB	Output is correct
2	Correct	1 ms	300 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	27 ms	8612 KB	Output is correct
5	Correct	33 ms	10440 KB	Output is correct
6	Correct	36 ms	10060 KB	Output is correct
7	Correct	35 ms	10404 KB	Output is correct
8	Correct	235 ms	77860 KB	Output is correct
9	Correct	473 ms	132812 KB	Output is correct
10	Correct	490 ms	148644 KB	Output is correct
11	Correct	530 ms	161112 KB	Output is correct
12	Correct	529 ms	166584 KB	Output is correct
13	Correct	584 ms	207216 KB	Output is correct
14	Correct	503 ms	209356 KB	Output is correct
15	Runtime error	501 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-