Submission #574621

#	Time	Username	Problem	Language	Result	Execution time	Memory
574621		penguinhacker	Weighting stones (IZhO11_stones)	C++14	100 / 100	45 ms	4344 KiB

stones

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n;

struct {
	int mn[1<<18], mx[1<<18], lz[1<<18];
	void psh(int u, int l, int r) {
		if (lz[u]) {
			mn[u]+=lz[u], mx[u]+=lz[u];
			if (l!=r)
				lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
			lz[u]=0;
		}
	}
	void upd(int ql, int qr, int x, int u=1, int l=0, int r=n-1) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return;
		if (ql<=l&&r<=qr) {
			lz[u]+=x;
			psh(u, l, r);
			return;
		}
		int mid=(l+r)/2;
		upd(ql, qr, x, 2*u, l, mid);
		upd(ql, qr, x, 2*u+1, mid+1, r);
		mn[u]=min(mn[2*u], mn[2*u+1]);
		mx[u]=max(mx[2*u], mx[2*u+1]);
	}
} st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int q=0; q<n; ++q) {
		int i, t;
		cin >> i >> t, --i;
		st.upd(0, i, t==1?1:-1);
		//cout << st.mx[1] << " " << st.mn[1] << "\n";
		cout << (st.mx[1]>0?st.mn[1]<0?'?':'>':'<') << "\n";
	}
	return 0;
}

• Subtask 1: 100 / 100