Submission #116621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116621	2019-06-13T07:32:45 Z	nandonathaniel	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	110 ms	3192 KB

apple

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

struct Node{
	LL L,R,value;
	bool lazy;
	Node *left,*right;
	void reset(){
		value=0;
		lazy=0;
		left=NULL;
		right=NULL;
	}
	LL query(LL x,LL y){
		if(L>=x && R<=y)return value;
		if(L>y || R<x)return 0;
		if(lazy)return min(R,y)-max(L,x)+1;
		LL ans=0;
		if(left!=NULL)ans+=left->query(x,y);
		if(right!=NULL)ans+=right->query(x,y);
		return ans;
	}
	void update(LL x,LL y){
		if(L>=x && R<=y){
			lazy=1;
			value=R-L+1;
			return;
		}
		if(L>y || R<x)return;
		if(lazy)return;
		if(left==NULL){
			left=new Node;
			left->reset();
			left->L=L;
			left->R=(L+R)/2;
			left->value=0;
			left->lazy=0;
		}
		if(right==NULL){
			right=new Node;
			right->reset();
			right->L=(L+R)/2+1;
			right->R=R;
			right->value=0;
			right->lazy=0;
		}
		left->update(x,y);
		right->update(x,y);
		value=left->value+right->value;
	}
}root;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL m,c=0,op,x,y;
	cin >> m;
	root.L=1;
	root.R=1e9;
	while(m--){
		cin >> op >> x >> y;
		x+=c;y+=c;
		if(op==1){
			c=root.query(x,y);
			cout << c << endl;
		}
		else root.update(x,y);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	11 ms	464 KB	Output is correct
5	Correct	13 ms	640 KB	Output is correct
6	Correct	17 ms	524 KB	Output is correct
7	Correct	13 ms	640 KB	Output is correct
8	Correct	54 ms	1440 KB	Output is correct
9	Correct	107 ms	2552 KB	Output is correct
10	Correct	105 ms	2680 KB	Output is correct
11	Correct	104 ms	2652 KB	Output is correct
12	Correct	104 ms	2676 KB	Output is correct
13	Correct	110 ms	3064 KB	Output is correct
14	Correct	109 ms	3024 KB	Output is correct
15	Correct	104 ms	3068 KB	Output is correct
16	Correct	107 ms	3184 KB	Output is correct
17	Correct	98 ms	2936 KB	Output is correct
18	Correct	98 ms	2936 KB	Output is correct
19	Correct	102 ms	3160 KB	Output is correct
20	Correct	102 ms	3192 KB	Output is correct