Submission #4851

#	Time	Username	Problem	Language	Result	Execution time	Memory
4851		cki86201	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	60 ms	1208 KiB

apple

#include<stdio.h>
#include<algorithm>

struct segment{
	int x;
	segment *link[2];
	void update(int s,int d,int l,int r)
	{
		if(x == d-s+1)return;
		if(l<=s && d<=r){
			x = d-s+1;
			return;
		}
		int m = (s+d)>>1;
		if(l<=m){
			if(!link[0])link[0] = new segment();
			link[0]->update(s,m,l,r);
		}
		if(r>m){
			if(!link[1])link[1] = new segment();
			link[1]->update(m+1,d,l,r);
		}
		x = (link[0]?link[0]->x:0) + (link[1]?link[1]->x:0);
	}
	int read(int s,int d,int l,int r)
	{
		if(l<=s && d<=r)return x;
		if(x == d-s+1)return std::min(d,r) - std::max(s,l) + 1;
		int m = (s+d)>>1, ret = 0;
		if(l<=m)ret += link[0]?link[0]->read(s,m,l,r):0;
		if(r>m)ret += link[1]?link[1]->read(m+1,d,l,r):0;
		return ret;
	}
}root;

int main(){
	int n,c=0;
	scanf("%d",&n);
	while(n--){
		int d,x,y;
		scanf("%d%d%d",&d,&x,&y);
		if(d==1)printf("%d\n",c = root.read(1,1e9,x+c,y+c));
		else root.update(1,1e9,x+c,y+c);
	}
	return 0;
}

• Subtask 1: 100 / 100