Submission #4872

#	Time	Username	Problem	Language	Result	Execution time	Memory
4872		ainta	Weighting stones (IZhO11_stones)	C++98	100 / 100	69 ms	4156 KiB

stones

#include<stdio.h>
#include<algorithm>
using namespace std;
#define SZ 131072
int n;
struct ST{
	int M, m, K;
}IT[SZ * 2];
void Add2(int node, int x){
	IT[node].K += x, IT[node].M += x, IT[node].m += x;
}
void Add(int node, int b, int e, int s, int l, int x){
	if (b == s && e == l){
		Add2(node, x);
		return;
	}
	Add2(node * 2, IT[node].K);
	Add2(node * 2 + 1, IT[node].K);
	IT[node].K = 0;
	int m = (b + e) >> 1;
	if (s <= m)Add(node * 2, b, m, s, min(l, m), x);
	if (l > m)Add(node * 2 + 1, m + 1, e, max(s, m + 1), l, x);
	IT[node].m = min(IT[node * 2].m, IT[node * 2 + 1].m);
	IT[node].M = max(IT[node * 2].M, IT[node * 2 + 1].M);
}
int main(){
	int i, a, b;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d", &a, &b);
		if (b == 1) Add(1, 1, SZ, 1, a, 1);
		else Add(1, 1, SZ, 1, a, -1);
		if (IT[1].m >= 0)printf(">\n");
		else if (IT[1].M <= 0)printf("<\n");
		else printf("?\n");
	}
}

• Subtask 1: 100 / 100