Submission #1078006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078006		Acanikolic	Weighting stones (IZhO11_stones)	C++14	100 / 100	61 ms	7576 KiB

stones

#include <bits/stdc++.h>  

#define int long long 

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 1e9 + 7;
 
const int inf = 1e9;

struct Node {
	int mn,mx;
};

Node st[N * 4];
int lazy[N * 4];

void push(int node,int tl,int tr) {
	st[node].mx += lazy[node];
	st[node].mn += lazy[node];
	if(tl != tr) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
}

void modify(int node,int tl,int tr,int l,int r,int val) {
	push(node,tl,tr);
	if(tl > r || tr < l) return;
	if(tl >= l && tr <= r) {
		lazy[node] = val;
		push(node,tl,tr);
		return;
	} 
	int mid = (tl + tr) / 2;
	modify(node * 2,tl,mid,l,r,val);
	modify(node * 2 + 1,mid + 1,tr,l,r,val);
	st[node].mn = min(st[node * 2].mn,st[node * 2 + 1].mn);
	st[node].mx = max(st[node * 2].mx,st[node * 2 + 1].mx);
}

int getmn(int node,int tl,int tr,int l,int r) {
	push(node,tl,tr);
	if(tl > r || tr < l) return inf;
	if(tl >= l && tr <= r) return st[node].mn;
	int mid = (tl + tr) / 2;
	return min(getmn(node * 2,tl,mid,l,r),getmn(node * 2 + 1,mid + 1,tr,l,r));
}

int getmx(int node,int tl,int tr,int l,int r) {
	push(node,tl,tr);
	if(tl > r || tr < l) return -inf;
	if(tl >= l && tr <= r) return st[node].mx;
	int mid = (tl + tr) / 2;
	return max(getmx(node * 2,tl,mid,l,r),getmx(node * 2 + 1,mid + 1,tr,l,r));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
 	int n;
 	cin >> n;
 	for(int i = 1; i <= n; i++) {
 		int x,y;
 		cin >> x >> y;
 		x = n - x + 1;
 		modify(1,1,n,x,n,(y == 1 ? 1 : -1));
 		if(getmn(1,1,n,1,n) >= 0) {
 			cout << ">\n";
 		}else if(getmx(1,1,n,1,n) <= 0) {
 			cout << "<\n";
 		}else {
 			cout << "?\n";
 		}
 	}
    return 0;
}

• Subtask 1: 100 / 100