Submission #1108163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108163		Tsagana	Weighting stones (IZhO11_stones)	C++14	0 / 100	1 ms	2384 KiB

stones

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct lf1 {
	int an;
	int ah;

	void set(int x) {
		an = ah = 0;
		if (x == 1) an = 1;
		else ah = 1;
	}
	void merge(lf1 x, lf1 y) {
		an = x.an; ah = y.ah;
		if (y.an < x.ah) ah += x.ah-y.an;
		else an += y.an-y.ah;
	}
};
struct lf2 {
	int an;
	int ah;

	void set(int x) {
		an = ah = 0;
		if (x == 1) an = 1;
		else ah = 1;
	}
	void merge(lf2 x, lf2 y) {
		an = y.an; ah = x.ah;
		if (y.ah < x.an) an += x.an-y.ah;
		else ah += y.ah-x.an;
	}
};

int n;
pair<int, int> mx;
lf1 S1[400001];
lf2 S2[400001];

void update(int id, int L, int R, int i, int k) {
	if (L == R) {S2[id].set(k); S1[id].set(k); return ;}
	int M = (L+R)/2, x = 2*id, y = x+1;
	if (i <= M) update(x, L, M, i, k);
	else update(y, M+1, R, i, k);
	S1[id].merge(S1[x], S1[y]);
	S2[id].merge(S2[x], S2[y]);
} void update(int i, int k) {update(1, 1, n, i, k);}

void solve () {
	cin >> n;
	mx = {0, 0};
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		if (mx.F < a) mx = {a, b};
		update(a, b);

		//cout << mx.S << ' ' << S1[1].an << ' ' << S1[1].ah << ' ' << S2[1].an << ' ' << S2[1].ah << '\n';

		if (mx.S == 1) cout << (!S1[1].ah ? ">\n" : "?\n");
		else cout << (!S2[1].an ? "<\n" : "?\n");
	}
}
int main() {IOS solve(); return 0;}

• Subtask 1: 0 / 100