제출 #4851

#제출 시각아이디문제언어결과실행 시간메모리
4851cki86201원숭이와 사과 나무 (IZhO12_apple)C++98
100 / 100
60 ms1208 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...