Submission #129062

#	Time	Username	Problem	Language	Result	Execution time	Memory
129062		keko37	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1172 ms	186724 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;

const int MAXN = 200005;

int n, m, len, ofs, cnt, xmn, xmx, ymn, ymx;
vector <int> ff[MAXN], vv[MAXN], ex[MAXN], ey[MAXN];
int lef[MAXN * 80], rig[MAXN * 80], t[MAXN * 80];
int ffr[MAXN], vvr[MAXN], exr[MAXN], eyr[MAXN];

void ispis (int x, int d) {
	if (x == 0) return;
	for (int i=0; i<d; i++) cout << ' ';
	cout << x << " " << t[x] << endl;
	ispis(lef[x], d + 1);
	ispis(rig[x], d + 1);
}

void obradi () {
	for (int i=0; i<n; i++) {
		sort(ff[i].begin(), ff[i].end());
		ff[i].erase(unique(ff[i].begin(), ff[i].end()), ff[i].end());
		for (auto j : ff[i]) {
			vv[i].push_back(j); vv[i].push_back(j+1);
			vv[i+1].push_back(j); vv[i+1].push_back(j+1);
			ex[i].push_back(j); ex[i+1].push_back(j);
			ey[j].push_back(i); ey[j+1].push_back(i);
		}
	}
	for (int i=0; i<=n; i++) {
		sort(vv[i].begin(), vv[i].end());
		vv[i].erase(unique(vv[i].begin(), vv[i].end()), vv[i].end());
		sort(ex[i].begin(), ex[i].end());
		ex[i].erase(unique(ex[i].begin(), ex[i].end()), ex[i].end());
	}
	for (int i=0; i<=m; i++) {
		sort(ey[i].begin(), ey[i].end());
		ey[i].erase(unique(ey[i].begin(), ey[i].end()), ey[i].end());
	}
}

int build (int len) {
	int curr = ++cnt;
	if (len == 1) return curr;
	lef[curr] = build(len/2);
	rig[curr] = build(len/2);
	return curr;
}

int update (int x, int pos, int lo, int hi) {
	int curr = ++cnt;
	if (lo == hi) {
		t[curr] = t[x] + 1;
		return curr;
	}
	int mid = (lo + hi) / 2;
	if (pos <= mid) {
		lef[curr] = update(lef[x], pos, lo, mid);
		rig[curr] = rig[x];
	} else {
		lef[curr] = lef[x];
		rig[curr] = update(rig[x], pos, mid+1, hi);
	}
	t[curr] = t[lef[curr]] + t[rig[curr]];
	return curr;
}

int upit (int x, int from, int to, int lo, int hi) {
	if (from <= lo && hi <= to) return t[x];
	if (to < lo || hi < from) return 0;
	return upit(lef[x], from, to, lo, (lo + hi)/2) + upit(rig[x], from, to, (lo + hi)/2+1, hi);
}

void tour_init () {
	ofs = 1;
	while (ofs < max(m+1, n+1)) ofs *= 2;
	ffr[0] = build(ofs); vvr[0] = build(ofs);
	exr[0] = build(ofs); eyr[0] = build(ofs);
	for (int i=0; i<n; i++) {
		if (i > 0) ffr[i] = ffr[i-1];
		for (auto j : ff[i]) {
			ffr[i] = update(ffr[i], j, 0, ofs-1);
		}
	}
	for (int i=0; i<=n; i++) {
		if (i > 0) vvr[i] = vvr[i-1];
		for (auto j : vv[i]) {
			vvr[i] = update(vvr[i], j, 0, ofs-1);
		}
		if (i > 0) exr[i] = exr[i-1];
		for (auto j : ex[i]) {
			exr[i] = update(exr[i], j, 0, ofs-1);
		}
	}
	for (int i=0; i<=m; i++) {
		if (i > 0) eyr[i] = eyr[i-1];
		for (auto j : ey[i]) {
			eyr[i] = update(eyr[i], j, 0, ofs-1);
		}
	}
}

void init (int R, int C, int sx, int sy, int M, char *S) {
	n = R; m = C; len = M;
	sx--; sy--;
	xmn = xmx = sx;
	ymn = ymx = sy;
	ff[sx].push_back(sy);
	for (int i=0; i<len; i++) {
		if (S[i] == 'N') sx--;
		if (S[i] == 'E') sy++;
		if (S[i] == 'S') sx++;
		if (S[i] == 'W') sy--;
		xmn = min(xmn, sx); xmx = max(xmx, sx);
		ymn = min(ymn, sy); ymx = max(ymx, sy);
		ff[sx].push_back(sy);
	}
	obradi();
	tour_init();
}

int colour (int x1, int y1, int x2, int y2) {
	x1--; y1--; x2--; y2--;
	int f = 0, v = 0, e = 0;
	f = upit(ffr[x2], y1, y2, 0, ofs-1) - (x1 == 0 ? 0 : upit(ffr[x1-1], y1, y2, 0, ofs-1));
	if (x1 < x2 && y1 < y2) v = upit(vvr[x2], y1+1, y2, 0, ofs-1) - upit(vvr[x1], y1+1, y2, 0, ofs-1);
	if (x1 < x2) e += upit(exr[x2], y1, y2, 0, ofs-1) - upit(exr[x1], y1, y2, 0, ofs-1);
	if (y1 < y2) e += upit(eyr[y2], x1, x2, 0, ofs-1) - upit(eyr[y1], x1, x2, 0, ofs-1);
    return e + 1 - v - f + (x1 < xmn && xmx < x2 && y1 < ymn && ymx < y2);
}

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