Submission #913903

#	Time	Username	Problem	Language	Result	Execution time	Memory
913903		daoquanglinh2007	Weighting stones (IZhO11_stones)	C++17	100 / 100	39 ms	5616 KiB

stones

#include <bits/stdc++.h>
using namespace std;
 
const int NM = 1e5;
 
struct node{
	int mn, mx;
};
 
int N;
node st[4*NM+5];
int lazy[4*NM+5];
 
void apply(int id, int val){
	st[id].mn += val;
	st[id].mx += val;
}
 
void down(int id){
	apply(2*id, lazy[id]); apply(2*id+1, lazy[id]);
	lazy[2*id] += lazy[id], lazy[2*id+1] += lazy[id];
	lazy[id] = 0;
}
 
node operator + (node a, node b){
	node c;
	c.mn = min(a.mn, b.mn);
	c.mx = max(a.mx, b.mx);
	return c;
}
 
void update(int id, int l, int r, int u, int v, int val){
	if (v < l || u > r) return;
	if (l >= u && r <= v){
		apply(id, val);
		lazy[id] += val;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	update(2*id, l, mid, u, v, val);
	update(2*id+1, mid+1, r, u, v, val);
	st[id] = st[2*id]+st[2*id+1];
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++){
		int R, S; cin >> R >> S;
		R = N-R+1;
		if (S == 1){
			update(1, 1, N, R, N, 1);
		}
		else{
			update(1, 1, N, R, N, -1);
		}
		if (st[1].mn >= 0) cout << '>';
		else if (st[1].mx <= 0) cout << '<';
		else cout << '?';
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100