Submission #334316

#	Time	Username	Problem	Language	Result	Execution time	Memory
334316		nandonathaniel	Weighting stones (IZhO11_stones)	C++14	100 / 100	74 ms	5612 KiB

stones

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;

int tree[2][4*MAXN],lazy[2][4*MAXN];

void updatenode(int no,int now,int L,int R,int val){
	tree[no][now]+=val;
	lazy[no][now]+=val;
}

void pushdown(int no,int now,int L,int R){
	int mid=(L+R)/2;
	updatenode(no,2*now,L,mid,lazy[no][now]);
	updatenode(no,2*now+1,mid+1,R,lazy[no][now]);
	lazy[no][now]=0;
}

int query(int no,int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[no][now];
	if(L>y || R<x)return 0;
	pushdown(no,now,L,R);
	int mid=(L+R)/2;
	return max(query(no,2*now,L,mid,x,y),query(no,2*now+1,mid+1,R,x,y));
}

void update(int now,int L,int R,int x,int y,int val){
	if(L>=x && R<=y){
		updatenode(0,now,L,R,val);
		updatenode(1,now,L,R,val);
		return;
	}
	if(L>y || R<x)return;
	int mid=(L+R)/2;
	pushdown(0,now,L,R);
	pushdown(1,now,L,R);
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[0][now]=min(tree[0][2*now],tree[0][2*now+1]);
	tree[1][now]=max(tree[1][2*now],tree[1][2*now+1]);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,id,x;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x >> id;
		if(id==1){
			update(1,1,n,1,x,1);
		}
		else{
			update(1,1,n,1,x,-1);
		}
		int besar=query(1,1,1,n,1,n),kecil=query(0,1,1,n,1,n);
		if(besar>0){
			if(kecil>=0)cout << '>';
			else cout << '?';
		}
		else{
			if(kecil<=0)cout << '<';
			else cout << '?';
		}
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100