Submission #214019

#	Time	Username	Problem	Language	Result	Execution time	Memory
214019		spdskatr	Land of the Rainbow Gold (APIO17_rainbow)	C++14	12 / 100	805 ms	197112 KiB

rainbow

#include "rainbow.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

class PersistentSegtree {
public:
	int st[10000000], lc[10000000], rc[10000000], cnt = 1;
	int heads[200005];
	void seg_inc(int n, int pn, int lo, int hi, int i, int v) {
		if (lo + 1 == hi) {
			st[n] = st[pn] + v;
			return;
		}
		lc[n] = lc[pn], rc[n] = rc[pn];
		int mid = (lo + hi) / 2;
		if (mid > i) {
			lc[n] = cnt++;
			seg_inc(lc[n], lc[pn], lo, mid, i, v);
		} else {
			rc[n] = cnt++;
			seg_inc(rc[n], rc[pn], mid, hi, i, v);
		}
		st[n] = st[lc[n]] + st[rc[n]];
	}
	int seg_sum(int n, int pn, int lo, int hi, int l, int r) {
		if (lo >= r || hi <= l) return 0;
		if (lo >= l && hi <= r) {
			return st[n] - st[pn];
		}
		int mid = (lo + hi) / 2;
		return seg_sum(lc[n], lc[pn], lo, mid, l, r) + seg_sum(rc[n], rc[pn], mid, hi, l, r);
	}
} st[4];
vector<int> rec[4][200005];
set<pii> water, vedges, hedges, verts;

void init(int R, int C, int sr, int sc, int M, char *S) {
	water.insert({ sr, sc });
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			sr -= 1;
		} else if (S[i] == 'S') {
			sr += 1;
		} else if (S[i] == 'E') {
			sc += 1;
		} else {
			sc -= 1;
		}
		water.insert({ sr, sc });
	}
	for (pii p : water) {
		verts.insert(p);
		verts.insert({ p.fi + 1, p.se });
		verts.insert({ p.fi, p.se + 1 });
		verts.insert({ p.fi + 1, p.se + 1 });
		vedges.insert(p);
		vedges.insert({ p.fi, p.se + 1 });
		hedges.insert(p);
		hedges.insert({ p.fi + 1, p.se });
		rec[0][p.fi].push_back(p.se);
	}
	for (pii p : verts) rec[1][p.fi].push_back(p.se);
	for (pii p : hedges) rec[2][p.fi].push_back(p.se);
	for (pii p : vedges) rec[3][p.fi].push_back(p.se);
	for (int j = 0; j < 4; j++) {
		for (int i = 1; i <= R; i++) {
			int node = st[j].heads[i-1];
			for (int x : rec[j][i]) {
				int nn = st[j].cnt++;
				st[j].seg_inc(nn, node, 1, 200005, x, 1);
				node = nn;
			}
			st[j].heads[i] = node;
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	int a = st[3].seg_sum(st[3].heads[br], st[3].heads[ar-1], 1, 200005, ac + 1, bc + 1);
	int b = st[2].seg_sum(st[2].heads[br], st[2].heads[ar], 1, 200005, ac, bc + 1);
	int c = st[1].seg_sum(st[1].heads[br], st[1].heads[ar], 1, 200005, ac + 1, bc + 1);
	int d = st[0].seg_sum(st[0].heads[br], st[0].heads[ar-1], 1, 200005, ac, bc + 1);
    return 1 + a + b - c - d;
}

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