Submission #93821

#	Time	Username	Problem	Language	Result	Execution time	Memory
93821		Noam527	Weighting stones (IZhO11_stones)	C++17	100 / 100	47 ms	4500 KiB

stones

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

struct segtree {
	int n;
	vector<int> tag, mn, mx;
	segtree() {}
	segtree(int sz) {
		n = sz + 1;
		while (n != (n&-n)) n += (n&-n);
		tag.resize(2 * n, 0);
		mn.resize(2 * n, 0);
		mx.resize(2 * n, 0);
	}
	void fix(int x) {
		if (x >= n) return;
		mn[x] = tag[x] + min(mn[2 * x + 1], mn[2 * x + 2]);
		mx[x] = tag[x] + max(mx[2 * x + 1], mx[2 * x + 2]);
	}
	void push(int x) {
		if (x >= n) return;
		for (auto i : { x + x + 1, x + x + 2 }) {
			tag[i] += tag[x];
			mn[i] += tag[x];
			mx[i] += tag[x];
		}
		tag[x] = 0;
	}
	void add(int pos, int val) {
		upd(pos, n - 1, val, 0, 0, n - 1);
	}
	void upd(int l, int r, int val, int node, int nl, int nr) {
		if (nr < l || r < nl) return;
		if (l <= nl && nr <= r) {
			tag[node] += val;
			mn[node] += val;
			mx[node] += val;
			return;
		}
		int mid = (nl + nr) / 2;
		upd(l, r, val, 2 * node + 1, nl, mid);
		upd(l, r, val, 2 * node + 2, mid + 1, nr);
		fix(node);
	}
	int m() {
		return mn[0];
	}
	int M() {
		return mx[0];
	}
};

int n, p[2];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	segtree T(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> p[0] >> p[1];
		p[1] = 2 * p[1] - 3;
		sum += p[1];
		T.add(p[0], p[1]);
		if (T.m() == sum) cout << ">\n";
		else if (T.M() == sum) cout << "<\n";
		else cout << "?\n";
	}
}

• Subtask 1: 100 / 100