Submission #5001

#	Time	Username	Problem	Language	Result	Execution time	Memory
5001		cki86201	Weighting stones (IZhO11_stones)	C++98	100 / 100	68 ms	4156 KiB

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