Submission #627578

#	Time	Username	Problem	Language	Result	Execution time	Memory
627578		MilosMilutinovic	Weighting stones (IZhO11_stones)	C++14	100 / 100	95 ms	10068 KiB

stones

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

struct segt
{
	struct node {
		int a[4] = {0, 0, 0, 0};
	} dat[400005];
	node comb(node L, node R) {
		node ret;
		ret.a[0] = L.a[0] + R.a[0];
		ret.a[1] = L.a[1] + R.a[1];
		ret.a[2] = max(L.a[2] + R.a[0] - R.a[1], R.a[2]);
		ret.a[3] = max(L.a[3] + R.a[1] - R.a[0], R.a[3]);
		return ret;
	}
	void modify(int idx, int v, int cv = 1, int cl = 0, int cr = 100005) {
		if(cl == cr) {
			dat[cv].a[v] ++;
			dat[cv].a[2] = max(0, dat[cv].a[0] - dat[cv].a[1]);
			dat[cv].a[3] = max(0, dat[cv].a[1] - dat[cv].a[0]);
			return;
		}
		int mid = cl + cr >> 1;
		if(idx <= mid) modify(idx, v, cv << 1, cl, mid);
		else modify(idx, v, cv << 1 | 1, mid + 1, cr);
		dat[cv] = comb(dat[cv << 1], dat[cv << 1 | 1]);
	}
	node query(int ql, int qr, int cv = 1, int cl = 0, int cr = 100005) {
		if(cl > qr || cr < ql || cl > cr) return node();
		if(ql <= cl && cr <= qr) return dat[cv];
		int mid = cl + cr >> 1;
		return comb(query(ql, qr, cv << 1, cl, mid), query(ql, qr, cv << 1 | 1, mid + 1, cr));
	}
} tre;

int main()
{
	int n;
	scanf("%d", &n);
	set<PII> st;
	rep(i, n) {
		int r, s; scanf("%d%d", &r, &s); s --;
		st.insert({r, s});
		tre.modify(r, s);
		int win = prev(st.end())->second;
		if(tre.query(1, n).a[2 + 1 - win] > 0) puts("?");
		else puts(win == 0 ? ">" : "<");
	}
	return 0;
}

Compilation message (stderr)

stones.cpp: In member function 'void segt::modify(int, int, int, int, int)':
stones.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
stones.cpp: In member function 'segt::node segt::query(int, int, int, int, int)':
stones.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
stones.cpp: In function 'int main()':
stones.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
stones.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   int r, s; scanf("%d%d", &r, &s); s --;
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100