Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 11:53:26
Task:Coins
Sender:Ukkonen Fan Club
Submission time:2018-05-26 11:53:26
Status:READY
Result:ACCEPTED

Show test data

Code

#include <iostream>

const int N = 2 * 1e5;
int min[4 * N];
int max[4 * N];
int add[4 * N];
int h = 1;

void push(int i) {
	min[i] += add[i];
	max[i] += add[i];
	if (i < h) {
		add[2*i] += add[i];
		add[2*i+1] += add[i];
	}
	add[i] = 0;
}
void update(int i) {
	min[i] = std::min(min[2*i], min[2*i+1]);
	max[i] = std::max(max[2*i], max[2*i+1]);
}

void inc(int a, int b, int v, int i = 1, int ia = 0, int ib = h - 1) {
	push(i);
	if (b < ia || ib < a) return;
	if (a <=ia && ib<= b) {
		add[i] += v;
		push(i);
	} else {
		int mid = (ia + ib) >> 1;
		inc(a, b, v, 2 * i, ia, mid);
		inc(a, b, v, 2 * i + 1, mid + 1, ib);
		update(i);
	}
}

int main() {
	int n;
	std::cin >> n;
	while(h < n) h <<= 1;
	for (int i = 0; i < n; ++i) {
		int a, b;
		std::cin >> a >> b;
		a = (n - a);
		int v = (b == 1 ? 1 : -1);
		inc(a, n - 1, v);
		if (min[1] >= 0) {
			std::cout << ">\n";
		} else if (max[1] <= 0) {
			std::cout << "<\n";
		} else {
			std::cout << "?\n";
		}
	}
}