Submission #1072684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072684		pavement	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	634 ms	194748 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;

#define pb push_back
#define eb emplace_back

vector<int> row[200005], col[200005];
vector<ii> nodes, cells, horiz, vert;
int ptr;

struct node {
	node *left, *right;
	int S, E;
	vector<int> val;
	node(int _s, int _e, vector<ii> &vec) : S(_s), E(_e) {
		if (S == E) {
			while (ptr < (int)vec.size() && vec[ptr].first == S) {
				val.pb(vec[ptr].second);
				ptr++;
			}
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M, vec);
		right = new node(M + 1, E, vec);
		merge(left->val.begin(), left->val.end(), right->val.begin(), right->val.end(), back_inserter(val));
	}
	int qry(int l, int r, int x, int y) {
		if (l > E || r < S) {
			return 0;
		}
		if (l <= S && E <= r) {
			return upper_bound(val.begin(), val.end(), y) - lower_bound(val.begin(), val.end(), x);
		}
		return left->qry(l, r, x, y) + right->qry(l, r, x, y);
	}
} *root_nodes, *root_cells, *root_horiz, *root_vert;

void init(int R, int C, int sr, int sc, int M, char *S) {
	cells.eb(sr, sc);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			sr--;
		} else if (S[i] == 'S') {
			sr++;
		} else if (S[i] == 'E') {
			sc++;
		} else {
			sc--;
		}
		cells.eb(sr, sc);
	}
	sort(cells.begin(), cells.end());
	cells.erase(unique(cells.begin(), cells.end()), cells.end());
	for (const auto &[r, c] : cells) {
		//~ cout << "! " << r << ' ' << c << '\n';
		nodes.eb(r, c);
		nodes.eb(r + 1, c);
		nodes.eb(r, c + 1);
		nodes.eb(r + 1, c + 1);
		horiz.eb(r, c);
		horiz.eb(r + 1, c);
		vert.eb(r, c);
		vert.eb(r, c + 1);
	}
	for (auto *vec : {&nodes, &horiz, &vert}) {
		sort(vec->begin(), vec->end());
		vec->erase(unique(vec->begin(), vec->end()), vec->end());
	}
	//~ cout << "HERE" << endl;
	for (const auto &[r, c] : nodes) {
		//~ cout << r << ' ' << c << '\n';
		row[r].pb(c);
		col[c].pb(r);
	}
	for (int i = 1; i <= R; i++) {
		sort(row[i].begin(), row[i].end());
	}
	for (int i = 1; i <= C; i++) {
		sort(col[i].begin(), col[i].end());
	}
	root_nodes = new node(1, R, nodes);
	ptr = 0;
	root_cells = new node(1, R, cells);
	ptr = 0;
	root_horiz = new node(1, R, horiz);
	ptr = 0;
	root_vert = new node(1, R, vert);
	//~ cout << "HERE" << endl;
}

int colour(int ar, int ac, int br, int bc) {
	int V = (br - ar + 1) * 2 + (bc - ac + 1) * 2 - 4, E = V;
	bool border = 0;
	for (int tmp_r : {ar, br + 1}) {
		auto it = lower_bound(row[tmp_r].begin(), row[tmp_r].end(), ac);
		if (it != row[tmp_r].end() && *it <= bc + 1) {
			border = 1;
		}
	}
	for (int tmp_c : {ac, bc + 1}) {
		auto it = lower_bound(col[tmp_c].begin(), col[tmp_c].end(), ar);
		if (it != col[tmp_c].end() && *it <= br + 1) {
			border = 1;
		}
	}
	V += root_nodes->qry(ar + 1, br, ac + 1, bc);
	//~ for (const auto &[r, c] : nodes) {
		//~ if (ar + 1 <= r && r <= br && ac + 1 <= c && c <= bc) {
			//~ V++;
		//~ }
	//~ }
	if (!border) {
		bool wraps = root_cells->qry(ar, br, ac, bc);
		//~ for (const auto &[r, c] : cells) {
			//~ if (ar <= r && r <= br && ac <= c && c <= bc) {
				//~ wraps = 1;
			//~ }
		//~ }
		if (!wraps) {
			return 1;
		}
		V = nodes.size();
		E = horiz.size() + vert.size();
		int F = 2 - (V - E), water_F = cells.size();
		return F - water_F;
	}
	E += root_horiz->qry(ar + 1, br, ac, bc);
	//~ for (const auto &[r, c] : horiz) {
		//~ if (ar + 1 <= r && r <= br && ac <= c && c <= bc) {
			//~ E++;
		//~ }
	//~ }
	E += root_vert->qry(ar, br, ac + 1, bc);
	//~ for (const auto &[r, c] : vert) {
		//~ if (ar <= r && r <= br && ac + 1 <= c && c <= bc) {
			//~ E++;
		//~ }
	//~ }
	int F = 2 - (V - E), water_F = root_cells->qry(ar, br, ac, bc);
	//~ for (const auto &[r, c] : cells) {
		//~ if (ar <= r && r <= br && ac <= c && c <= bc) {
			//~ water_F++;
		//~ }
	//~ }
	return F - water_F - 1;
}

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