Submission #5001

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5001	2014-01-25T04:57:41 Z	cki86201	Weighting stones (IZhO11_stones)	C++	100 / 100	68 ms	4156 KB

stones

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

struct tree{
	inline void upd(int i){n+=i,x+=i,c+=i;}
	int n,x;
	int c;
}T[1<<18];

void update(int x,int idx,int l,int r,int root)
{
	if(r<=x){
		T[root].upd(idx);
		return;
	}
	T[root<<1].upd(T[root].c);
	T[root<<1|1].upd(T[root].c);
	T[root].c = 0;
	int m = (l+r)>>1;
	update(x,idx,l,m,root<<1);
	if(x>m)update(x,idx,m+1,r,root<<1|1);
	T[root].n = std::min(T[root<<1].n, T[root<<1|1].n);
	T[root].x = std::max(T[root<<1].x, T[root<<1|1].x);
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		if(y==1)update(x,1,1,n,1);
		else update(x,-1,1,n,1);
		if(T[1].n>=0)printf(">\n");
		else if(T[1].x<=0)printf("<\n");
		else printf("?\n");
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4156 KB	Output is correct - 73 tokens
2	Correct	0 ms	4156 KB	Output is correct - 89 tokens
3	Correct	0 ms	4156 KB	Output is correct - 221 tokens
4	Correct	0 ms	4156 KB	Output is correct - 21 tokens
5	Correct	0 ms	4156 KB	Output is correct - 369 tokens
6	Correct	0 ms	4156 KB	Output is correct - 492 tokens
7	Correct	0 ms	4156 KB	Output is correct - 945 tokens
8	Correct	0 ms	4156 KB	Output is correct - 1237 tokens
9	Correct	0 ms	4156 KB	Output is correct - 1105 tokens
10	Correct	5 ms	4156 KB	Output is correct - 8921 tokens
11	Correct	31 ms	4156 KB	Output is correct - 56110 tokens
12	Correct	56 ms	4156 KB	Output is correct - 90207 tokens
13	Correct	45 ms	4156 KB	Output is correct - 100000 tokens
14	Correct	56 ms	4156 KB	Output is correct - 100000 tokens
15	Correct	51 ms	4156 KB	Output is correct - 100000 tokens
16	Correct	63 ms	4156 KB	Output is correct - 100000 tokens
17	Correct	42 ms	4156 KB	Output is correct - 100000 tokens
18	Correct	55 ms	4156 KB	Output is correct - 99999 tokens
19	Correct	58 ms	4156 KB	Output is correct - 99999 tokens
20	Correct	57 ms	4156 KB	Output is correct - 99999 tokens
21	Correct	65 ms	4156 KB	Output is correct - 100000 tokens
22	Correct	68 ms	4156 KB	Output is correct - 100000 tokens
23	Correct	58 ms	4156 KB	Output is correct - 100000 tokens
24	Correct	56 ms	4156 KB	Output is correct - 100000 tokens
25	Correct	57 ms	4156 KB	Output is correct - 100000 tokens