Submission #274279

#	Time	Username	Problem	Language	Result	Execution time	Memory
274279		srvlt	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1691 ms	304704 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include "rainbow.h"

int r, c;
map <array <int, 2>, int> used[3];

struct Node {
	int n;
	vector <int> xv, val, val_cell;
	vector <array <int, 2>> pt;
	void add(int x, int v) {
		xv.pb(x);
		pt.pb({x, v});
	}
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - begin(xv));
	}
	void build() {
		cps(xv);
		n = SZ(xv);
		val.resize(n), val_cell.resize(n);
		for (auto & i : pt) {
			int x = pos(i[0]);
			if (i[1] == 0) val[x]--;
			if (i[1] == 1) val[x]++;
			if (i[1] == 2) val_cell[x]++;
		}
		for (int i = 1; i < n; i++) {
			val[i] += val[i - 1];
			val_cell[i] += val_cell[i - 1];
		}
	}
	int get(int l, int r) {
		l = pos(l), r = pos(r + 1) - 1;
		if (l > r) return 0;
		if (l == 0) return val[r];
		return val[r] - val[l - 1];
	}
	int get_cell(int l, int r) {
		l = pos(l), r = pos(r + 1) - 1;
		if (l > r) return 0;
		if (l == 0) return val_cell[r];
		return val_cell[r] - val_cell[l - 1];
	}
};

struct SegTree {
	int n;
	vector <int> xv;
	vector <array <int, 3>> pt;
	vector <Node> nd;
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - xv.begin());
	}
	void add(int x, int y, int v) {
		for (x += n; x > 0; x >>= 1) nd[x].add(y, v);
	}
	void build() {
		for (auto & i : pt) xv.pb(i[0]);
		cps(xv);
		n = 1;
		while (n < SZ(xv)) n <<= 1;
		nd.resize(n << 1);
		for (auto & i : pt) {
			int x = pos(i[0]);
			add(x, i[1], i[2]);
		}
		for (int i = 1; i < (n << 1); i++) nd[i].build();
	}
	int get(int l, int r, int l2, int r2) {
		l = pos(l), r = pos(r + 1);
		if (l > r || l2 > r2) return 0;
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += nd[--r].get(l2, r2);
			if (l & 1) res += nd[l++].get(l2, r2);
		}
		return res;
	}
	int get_cell(int l, int r, int l2, int r2) {
		l = pos(l), r = pos(r + 1);
		if (l > r || l2 > r2) return 0;
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += nd[--r].get_cell(l2, r2);
			if (l & 1) res += nd[l++].get_cell(l2, r2);
		}
		return res;
	}
};
SegTree plane;

void set_pt(int x, int y) {
	if (used[0].count({x, y})) return;
	used[0][{x, y}] = 1;
	plane.pt.pb({x, y, 0});
}

void set_edge(int x, int y) {
	if (used[1].count({x, y})) return;
	used[1][{x, y}] = 1;
	plane.pt.pb({x, y, 1});
}

void set_cell(int x, int y) {
	if (used[2].count({x, y})) return;
	used[2][{x, y}] = 1;
	plane.pt.pb({x, y, 2});
}

void add(int x, int y) {
	x *= 2, y *= 2;
	set_cell(x - 1, y - 1);
	set_pt(x, y), set_pt(x - 2, y), set_pt(x, y - 2), set_pt(x - 2, y - 2);
	set_edge(x, y - 1), set_edge(x - 1, y), set_edge(x - 1, y - 2), set_edge(x - 2, y - 1);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R, c = C;
	int x = sr, y = sc;
	add(x, y);
	for (int i = 0; i < M; i++) {
		if (S[i] == 'N') x--;
		if (S[i] == 'S') x++;
		if (S[i] == 'W') y--;
		if (S[i] == 'E') y++;
		add(x, y);
	}
	plane.build();
}

int colour(int ar, int ac, int br, int bc) {
	ar--, ac--;
	ar *= 2, ac *= 2, br *= 2, bc *= 2;
	int cells = plane.get_cell(ar, br, ac, bc);
	int nb_cells = plane.get_cell(ar + 2, br - 2, ac + 2, bc - 2);
	int C = 2;
	if (cells > nb_cells || cells == 0) C = 1;
	int ve = plane.get(ar + 1, br - 1, ac + 1, bc - 1);
	int res = C + plane.get(ar + 1, br - 1, ac + 1, bc - 1) - cells;
    return res;
}

Compilation message (stderr)

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:147:6: warning: unused variable 've' [-Wunused-variable]
  147 |  int ve = plane.get(ar + 1, br - 1, ac + 1, bc - 1);
      |      ^~

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