Submission #732432

#	Time	Username	Problem	Language	Result	Execution time	Memory
732432		SanguineChameleon	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3051 ms	1048576 KiB

rainbow

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

struct BIT {
	set<pair<int, int>> S;
	vector<vector<int>> a;
	vector<vector<int>> tmp;
	vector<vector<int>> flag;
	int R, C;

	void init(int _R, int _C) {
		R = _R;
		C = _C;
		a.resize(R + 1);
		for (int i = 0; i <= R; i++) {
			a[i].resize(C + 1);
		}
	}

	void add(int x, int y) {
		if (x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) {
			return;
		}
		S.insert({x, y});
		a[x][y]++;
	}

	void build() {
		tmp = a;
		flag = a;
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				a[i][j] += a[i][j - 1];
			}
		}
		for (int j = 1; j <= C; j++) {
			for (int i = 1; i <= R; i++) {
				a[i][j] += a[i - 1][j];
			}
		}
	}

	int get(int x, int y) {
		return a[x][y];
	}

	long long get(int lx, int ly, int rx, int ry) {
		return 1LL * (rx - lx + 1) * (ry - ly + 1) - get(rx, ry) + get(rx, ly - 1) + get(lx - 1, ry) - get(lx - 1, ly - 1);
	}

	int bfs(int lx, int ly, int rx, int ry) {
		const int dx[4] = {-1, 1, 0, 0};
		const int dy[4] = {0, 0, -1, 1};
		for (int i = lx; i <= rx; i++) {
			for (int j = ly; j <= ry; j++) {
				flag[i][j] = false;
			}
		}
		int cnt = 0;
		for (int i = lx; i <= rx; i++) {
			for (int j = ly; j <= ry; j++) {
				if (!tmp[i][j] && !flag[i][j]) {
					flag[i][j] = true;
					cnt++;
					deque<pair<int, int>> q = {{i, j}};
					while (!q.empty()) {
						int cx = q.front().first;
						int cy = q.front().second;
						q.pop_front();
						for (int k = 0; k < 4; k++) {
							int nx = cx + dx[k];
							int ny = cy + dy[k];
							if (lx <= nx && nx <= rx && ly <= ny && ny <= ry && !tmp[nx][ny] && !flag[nx][ny]) {
								flag[nx][ny] = true;
								q.push_back({nx, ny});
							}
						}
					}
				}
			}
		}
		return cnt;
	}

} V, row_E, col_E, F;

int max_X, min_X, max_Y, min_Y;

void add(int cx, int cy) {
	max_X = max(max_X, cx);
	min_X = min(min_X, cx);
	max_Y = max(max_Y, cy);
	min_Y = min(min_Y, cy);
	V.add(cx, cy);
	row_E.add(cx - 1, cy);
	row_E.add(cx, cy);
	col_E.add(cx, cy - 1);
	col_E.add(cx, cy);
	F.add(cx - 1, cy - 1);
	F.add(cx - 1, cy);
	F.add(cx, cy - 1);
	F.add(cx, cy);
}

void init(int R, int C, int cx, int cy, int M, char *S) {
	V.init(R, C);
	row_E.init(R, C);
	col_E.init(R, C);
	F.init(R, C);
	max_X = cx;
	min_X = cx;
	max_Y = cy;
	min_Y = cy;
	add(cx, cy);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') {
			cx--;
		}
		if (S[i] == 'E') {
			cy++;
		}
		if (S[i] == 'S') {
			cx++;
		}
		if (S[i] == 'W') {
			cy--;
		}
		add(cx, cy);
	}
	V.build();
	row_E.build();
	col_E.build();
	F.build();
}

int colour(int lx, int ly, int rx, int ry) {
	if (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry) {
		return 1;
	}
	return V.bfs(lx, ly, rx, ry);
	//return V.get(lx, ly, rx, ry) - row_E.get(lx, ly, rx - 1, ry) - col_E.get(lx, ly, rx, ry - 1) + F.get(lx, ly, rx - 1, ry - 1);
}

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