oj.uz

Submission #4850

# Submission time Handle Problem Language Result Execution time Memory
4850 2014-01-05T08:34:38 Z cki86201 Monkey and Apple-trees (IZhO12_apple) C++
10 / 100
 52 ms 1212 KB 
#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-l,r-s)+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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 0 ms 1212 KB Output is correct
3 Incorrect 0 ms 1212 KB Output isn't correct
4 Incorrect 4 ms 1212 KB Output isn't correct
5 Incorrect 4 ms 1212 KB Output isn't correct
6 Incorrect 4 ms 1212 KB Output isn't correct
7 Incorrect 4 ms 1212 KB Output isn't correct
8 Incorrect 24 ms 1212 KB Output isn't correct
9 Incorrect 48 ms 1212 KB Output isn't correct
10 Incorrect 48 ms 1212 KB Output isn't correct
11 Incorrect 48 ms 1212 KB Output isn't correct
12 Incorrect 48 ms 1212 KB Output isn't correct
13 Incorrect 52 ms 1212 KB Output isn't correct
14 Incorrect 52 ms 1212 KB Output isn't correct
15 Incorrect 44 ms 1212 KB Output isn't correct
16 Incorrect 52 ms 1212 KB Output isn't correct
17 Incorrect 32 ms 1212 KB Output isn't correct
18 Incorrect 28 ms 1212 KB Output isn't correct
19 Incorrect 44 ms 1212 KB Output isn't correct
20 Incorrect 48 ms 1212 KB Output isn't correct