Submission #548633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548633	2022-04-14T04:27:25 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	535 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;
}
void pull(node *temp){
    temp->sum = temp->child[0]->sum + temp->child[1]->sum;
    temp->lazy = 0;
}
void push(node* v){
    if(v->lazy == 0 || v->tl == v->tr)return;
    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;
}
void update(int l,int r,node *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]);
	pull(v);
    }
}
int query(int l,int r,node* 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	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	28 ms	8532 KB	Output is correct
5	Correct	36 ms	10316 KB	Output is correct
6	Correct	35 ms	9936 KB	Output is correct
7	Correct	37 ms	10324 KB	Output is correct
8	Correct	235 ms	76812 KB	Output is correct
9	Correct	491 ms	130940 KB	Output is correct
10	Correct	509 ms	146764 KB	Output is correct
11	Correct	526 ms	159392 KB	Output is correct
12	Correct	530 ms	164696 KB	Output is correct
13	Correct	532 ms	205128 KB	Output is correct
14	Correct	511 ms	207240 KB	Output is correct
15	Runtime error	535 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-