Submission #116621

#	Time	Username	Problem	Language	Result	Execution time	Memory
116621		nandonathaniel	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	110 ms	3192 KiB

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 / 100