Submission #562181

#	Time	Username	Problem	Language	Result	Execution time	Memory
562181		hollwo_pelw	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1018 ms	77752 KiB

rainbow

#include "rainbow.h"

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

const int N = 2e5 + 5;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int min_X, min_Y, max_X, max_Y, tomap[1 << 8];

struct data_t {
	vector<pair<int, int>> list_val;
	vector<int> val[N];
	inline void pre_add(int x, int y) {
		// x -= min_X - 1, y -= min_Y - 1;
		list_val.emplace_back(x, y);
	}

	inline void work() {
		sort(list_val.begin(), list_val.end());
		list_val.erase(unique(list_val.begin(), list_val.end()), list_val.end());

		for (auto [x, y] : list_val) {
			for (; x < N; x += x & -x)
				val[x].push_back(y);
		}

		for (int i = 1; i < N; i++)
			sort(val[i].begin(), val[i].end());
	}

	inline int count(int p, int l, int r) {
		int res = 0;
		for (p = min(p, N - 1); p > 0; p -= p & -p) {
			res += upper_bound(val[p].begin(), val[p].end(), r)
				 - lower_bound(val[p].begin(), val[p].end(), l);
		}
		return res;
	}

	inline int count(int ax, int ay, int bx, int by) {
		// ax -= min_X - 1;
		// ay -= min_Y - 1;
		// bx -= min_X - 1;
		// by -= min_Y - 1;
		return count(bx, ay, by) - count(ax - 1, ay, by);
	}
} c11, c12, c21, c22;

void init(int X, int Y, int x, int y, int M, char *S) {
	tomap['N'] = 0;
	tomap['E'] = 1;
	tomap['S'] = 2;
	tomap['W'] = 3;

	vector<pair<int, int>> path;
	path.emplace_back(x, y);

	min_X = max_X = x;
	min_Y = max_Y = y;

	for (int i = 0; i < M; i++) {
		x += dx[tomap[S[i]]];
		y += dy[tomap[S[i]]];
		path.emplace_back(x, y);
	}

	for (auto [x, y] : path) {
		min_X = min(min_X, x);
		max_X = max(max_X, x);
		min_Y = min(min_Y, y);
		max_Y = max(max_Y, y);

		c11.pre_add(x, y);
		
		c12.pre_add(x, y);
		c12.pre_add(x, y + 1);

		c21.pre_add(x, y);
		c21.pre_add(x + 1, y);

		c22.pre_add(x, y);
		c22.pre_add(x, y + 1);
		c22.pre_add(x + 1, y);
		c22.pre_add(x + 1, y + 1);
	}

	c11.work();
	c12.work();
	c21.work();
	c22.work();
}

int colour(int ax, int ay, int bx, int by) {
	int res = (ax < min_X && ay < min_Y && bx > max_X && by > max_Y) ? 2 : 1;

	res -= c11.count(ax, ay, bx, by);
	res += c12.count(ax, ay + 1, bx, by);
	res += c21.count(ax + 1, ay, bx, by);
	res -= c22.count(ax + 1, ay + 1, bx, by);

	return res;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:64:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |   x += dx[tomap[S[i]]];
      |                 ~~~^
rainbow.cpp:65:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |   y += dy[tomap[S[i]]];
      |                 ~~~^

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