Submission #1113410

#TimeUsernameProblemLanguageResultExecution timeMemory
1113410ChinguunWeighting stones (IZhO11_stones)C++14
100 / 100
34 ms7676 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define meta int m = (L + R) / 2, x = i * 2 + 1, y = x + 1

const int N = 4e5 + 7;

int s[N], mx[N], mn[N];

void update (int i, int L, int R, int k, int v) {
	if (L == R) {
		s[i] = mx[i] = mn[i] = v;
		return;
	}
	meta;
	if (k <= m) update (x, L, m, k, v);
	else update (y, m + 1, R, k, v);
	s[i] = s[x] + s[y];
	mn[i] = min (mn[x] + s[y], mn[y]);
	mx[i] = max (mx[x] + s[y], mx[y]); 
	return;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y; cin >> x >> y; x--;
		if (y == 1) update (0, 0, n - 1, x, 1);
		else update (0, 0, n - 1, x, -1);

		if (mx[0] <= 0) cout << '<';
		else if (mn[0] >= 0) cout << '>';
		else cout << '?';
		cout << '\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...