Submission #17590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17590	2016-01-01T06:22:53 Z	Qwaz	Weighting stones (IZhO11_stones)	C++14	100 / 100	48 ms	5180 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5180 KB	Output is correct - 73 tokens
2	Correct	0 ms	5180 KB	Output is correct - 89 tokens
3	Correct	0 ms	5180 KB	Output is correct - 221 tokens
4	Correct	0 ms	5180 KB	Output is correct - 21 tokens
5	Correct	0 ms	5180 KB	Output is correct - 369 tokens
6	Correct	0 ms	5180 KB	Output is correct - 492 tokens
7	Correct	0 ms	5180 KB	Output is correct - 945 tokens
8	Correct	1 ms	5180 KB	Output is correct - 1237 tokens
9	Correct	0 ms	5180 KB	Output is correct - 1105 tokens
10	Correct	2 ms	5180 KB	Output is correct - 8921 tokens
11	Correct	10 ms	5180 KB	Output is correct - 56110 tokens
12	Correct	41 ms	5180 KB	Output is correct - 90207 tokens
13	Correct	37 ms	5180 KB	Output is correct - 100000 tokens
14	Correct	45 ms	5180 KB	Output is correct - 100000 tokens
15	Correct	21 ms	5180 KB	Output is correct - 100000 tokens
16	Correct	48 ms	5180 KB	Output is correct - 100000 tokens
17	Correct	14 ms	5180 KB	Output is correct - 100000 tokens
18	Correct	37 ms	5180 KB	Output is correct - 99999 tokens
19	Correct	43 ms	5180 KB	Output is correct - 99999 tokens
20	Correct	39 ms	5180 KB	Output is correct - 99999 tokens
21	Correct	45 ms	5180 KB	Output is correct - 100000 tokens
22	Correct	36 ms	5180 KB	Output is correct - 100000 tokens
23	Correct	24 ms	5180 KB	Output is correct - 100000 tokens
24	Correct	36 ms	5180 KB	Output is correct - 100000 tokens
25	Correct	37 ms	5180 KB	Output is correct - 100000 tokens