Submission #901171

#	Time	Username	Problem	Language	Result	Execution time	Memory
901171		LCJLY	Weighting stones (IZhO11_stones)	C++14	100 / 100	76 ms	17288 KiB

stones

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline pii combine(pii a, pii b){
	return {max(a.first,b.first),min(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v({0,0}),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_add(int x){
		v.first+=x;
		v.second+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd),r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m)l->rangeUpd(x,y,c);
		if(y>m)r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){	
	int n;
	cin >> n;
	
	int temp,temp2;
	node st(0,n+5);
	
	for(int x=0;x<n;x++){
		cin >> temp >> temp2;
		if(temp2==1){
			st.rangeUpd(1,temp,1);
		}
		else{
			st.rangeUpd(1,temp,-1);
		}
		
		pii hold=st.query(1,n);
		if(hold.first>=0&&hold.second>=0) cout << ">\n";
		else if(hold.first<=0&&hold.second<=0) cout << "<\n";
		else cout << "?\n";
	}
}	

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

		

• Subtask 1: 100 / 100