Submission #133809

#	Time	Username	Problem	Language	Result	Execution time	Memory
133809		mirbek01	Weighting stones (IZhO11_stones)	C++11	100 / 100	385 ms	4556 KiB

stones

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, mn[N * 4], mx[N * 4], b[N * 4];

void push(int v, int tl, int tr){
	if(tl != tr){
		b[v << 1] += b[v];
		b[v << 1 | 1] += b[v];
	}
	mx[v] += b[v];
	mn[v] += b[v];
	b[v] = 0;
}

void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n){
	push(v, tl, tr);
	if(l > tr || tl > r) 
		return ;
	if(l <= tl && tr <= r){
		b[v] += val;
		push(v, tl, tr);
		return ;
	}
	int tm = (tl + tr) >> 1;
	upd(l, r, val, v << 1, tl, tm);
	upd(l, r, val, v << 1 | 1, tm + 1, tr);
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
	mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
}

int main(){
	cin >> n;

	for(int i = 1; i <= n; i ++){
		int tp, x;
		cin >> x >> tp;
		if(tp == 1){
			upd(1, x, 1);
		} else {
			upd(1, x, -1);
		}
		if(mx[1] >= 0 && mn[1] >= 0)
			puts(">");
		else if(mx[1] <= 0 && mn[1] <= 0)
			puts("<");
		else 
			puts("?");
	}
}

• Subtask 1: 100 / 100