Submission #17590

#	Time	Username	Problem	Language	Result	Execution time	Memory
17590		Qwaz	Weighting stones (IZhO11_stones)	C++14	100 / 100	48 ms	5180 KiB

stones

#include <cstdio>
#include <algorithm>
using namespace std;

const int GAP = 131072;

struct node {
	int top1, bot1, top2, bot2;

	void merge(node &l, node &r) {
		//1 covers 2
		int delta1 = min(r.top1, l.bot2);
		top1 = l.top1 + r.top1 - delta1;
		bot2 = l.bot2 + r.bot2 - delta1;

		//2 covers 1
		int delta2 = min(r.top2, l.bot1);
		top2 = l.top2 + r.top2 - delta2;
		bot1 = l.bot1 + r.bot1 - delta2;
	}
};

int n;
node tree[GAP*2];

void update(int index) {
	index >>= 1;
	while (index) {
		tree[index].merge(tree[index*2], tree[index*2 + 1]);
		index >>= 1;
	}
}

void solve() {
	for (int i = 1; i <= n; i++) {
		int num, scale;
		scanf("%d%d", &num, &scale);

		if (scale == 1) {
			tree[GAP + num].top1++;
			tree[GAP + num].bot1++;
			update(GAP + num);
		} else {
			tree[GAP + num].top2++;
			tree[GAP + num].bot2++;
			update(GAP + num);
		}

		if (tree[1].bot1 == 0) puts("<");
		else if (tree[1].bot2 == 0) puts(">");
		else puts("?");
	}
}

int main() {
	scanf("%d", &n);

	solve();

	return 0;
}

• Subtask 1: 100 / 100