답안 #17590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17590 2016-01-01T06:22:53 Z Qwaz 돌 무게 재기 (IZhO11_stones) C++14
100 / 100
48 ms 5180 KB
#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;
}
# 결과 실행 시간 메모리 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