Submission #1108426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108426		Tsagana	Weighting stones (IZhO11_stones)	C++17	100 / 100	190 ms	5812 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 lf {
	int an1, ah1;
	int an2, ah2;

	void set(int x) {
		an1 = ah1 = 0;
		an2 = ah2 = 0;

		if (x == 1) an1 = an2 = 1;
		else ah1 = ah2 = 1;
	}
	void merge(lf x, lf y) {
		an1 = x.an1; ah1 = y.ah1;
		an2 = y.an2; ah2 = x.ah2;
		
		if (y.an1 < x.ah1) ah1 += x.ah1-y.an1;
		else an1 += y.an1-x.ah1;

		if (y.ah2 < x.an2) an2 += x.an2-y.ah2;
		else ah2 += y.ah2-x.an2;
	}
};

int n;
pair<int, int> mx;
lf S[400001];

void print(int i) {
	cout << i << ": " << S[i].an1 << ' ' << S[i].ah1 << " - ";
	cout << S[i].an2 << ' ' << S[i].ah2 << '\n';
} 
void build(int id, int L, int R) {
	print(id);
	if (L == R) {return ;}
	int M = (L+R)/2, x = 2*id, y = x+1;
	build(x, L, M);
	build(y, M+1, R);
}
void update(int id, int L, int R, int i, int k) {
	if (L == R) {S[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);
	S[id].merge(S[x], S[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);

		if (mx.S == 1) cout << (!S[1].ah1 ? ">\n" : "?\n");
		else cout << (!S[1].an2 ? "<\n" : "?\n");
	}
	//build(1, 1, n);
}
int main() {IOS solve(); return 0;}

• Subtask 1: 100 / 100