Submission #1209534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209534		k1r1t0	Land of the Rainbow Gold (APIO17_rainbow)	C++20	100 / 100	725 ms	264700 KiB

rainbow

#include <bits/stdc++.h>

using namespace std;

const int S = 4100000;
const int N = 210000;

struct segtree {
	struct node {
		int s, l, r;
		node(int s, int l, int r) : s(s), l(l), r(r) {}
		node() {s = l = r = 0;}
		node copy() {return {s, l, r};}
	};
	node vv[S];
	int rr[N], last;
	set<int> st[N];
	segtree() {
		last = 0;
	}
	void add(int r, int c) {
		st[r].insert(c);
	}
	void build() {
		for (int i = 1; i < N; i++) {
			rr[i] = rr[i - 1];
			for (int j : st[i])
				upd(rr[i], 1, N - 1, j);
		}
	}
	void upd(int &v, int l, int r, int k) {
		last++;
		vv[last] = vv[v].copy();
		v = last;
		vv[v].s++;
		if (l == r) return;
		int mid = (l + r) / 2;
		if (k <= mid) upd(vv[v].l, l, mid, k);
		else upd(vv[v].r, mid + 1, r, k);
	}
	int get(int &v, int l, int r, int ql, int qr) {
		if (qr < l || r < ql) return 0;
		if (ql <= l && r <= qr) return vv[v].s;
		int mid = (l + r) / 2;
		return get(vv[v].l, l, mid, ql, qr) + get(vv[v].r, mid + 1, r, ql, qr);
	}
	int get(int ar, int br, int ac, int bc) {
		if (br < ar || bc < ac) return 0;
		return get(rr[br], 1, N - 1, ac, bc) - get(rr[ar - 1], 1, N - 1, ac, bc);
	}
};

segtree cells, verts, edgesv, edgesh;
// cells - obv
// verts - (i, j) is left top corner of (i, j) cell
// edgesv - (i, j) is left edge of (i, j) cell
// edgesh - (i, j) is top edge of (i, j) cell
int minr, maxr, minc, maxc;

void add(int r, int c) {
	cells.add(r, c);
	verts.add(r, c);
	verts.add(r, c + 1);
	verts.add(r + 1, c);
	verts.add(r + 1, c + 1);
	edgesv.add(r, c);
	edgesv.add(r, c + 1);
	edgesh.add(r, c);
	edgesh.add(r + 1, c);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	minr = maxr = sr;
	minc = maxc = sc;
	add(sr, sc);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') sr--;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		if (S[i] == 'E') sc++;
		assert(1 <= sr && sr <= R && 1 <= sc && sc <= C);
		add(sr, sc);
		minr = min(minr, sr);
		maxr = max(maxr, sr);
		minc = min(minc, sc);
		maxc = max(maxc, sc);
	}
	cells.build();
	verts.build();
	edgesv.build();
	edgesh.build();
}

int colour(int ar, int ac, int br, int bc) {
	int C = 1;
	if (ar < minr && ac < minc && br > maxr && bc > maxc)
		C++;
	int B = cells.get(ar, br, ac, bc);
	int V = verts.get(ar + 1, br, ac + 1, bc);
	int E = edgesv.get(ar, br, ac + 1, bc) + edgesh.get(ar + 1, br, ac, bc);
	return C - V + E - B;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26