Submission #453572

#	Time	Username	Problem	Language	Result	Execution time	Memory
453572		dutch	Weighting stones (IZhO11_stones)	C++17	100 / 100	39 ms	4376 KiB

stones

#include <bits/stdc++.h>
using namespace std;
using T = array<int, 3>;

const T ID = {-1, 1, 0};

T comb(T &x, T &y){
	return {max(y[0], x[0] + y[2]), min(y[1], x[1] + y[2]), x[2] + y[2]};
}

int n, s = 1;
vector<T> a;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	while((s+=s)<n);
	a.assign(2*s, ID);

	while(n--){
		int i, v; cin >> i >> v;
		--i; v = 2*v-3;

		a[i+=s] = {v, v, v};
		while(i/=2) a[i] = comb(a[2*i], a[2*i+1]);

		if(a[1][0] > 0 && a[1][1] < 0) cout << "?\n";
		else cout << (a[1][0] > 0 ? "<\n" : ">\n");
	}
}

• Subtask 1: 100 / 100