Submission #544990

#	Time	Username	Problem	Language	Result	Execution time	Memory
544990		valerikk	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	965 ms	122772 KiB

rainbow

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

using namespace std;

struct Fenwick {
	int n;
	vector<vector<int> > ys;
	vector<vector<long long> > f;
	vector<int> nn;
	bool built;

	void fake_add(int x, int y) {
		assert(!built);
		for (int i = x + 1; i <= n; i += i & -i) {
			ys[i].emplace_back(y);
		}
	}

	void build() {
		assert(!built);
		for (int i = 0; i <= n; ++i) {
			sort(ys[i].begin(), ys[i].end());
			ys[i].resize(unique(ys[i].begin(), ys[i].end()) - ys[i].begin());
			nn[i] = ys[i].size();
			f[i].resize(nn[i] + 1);
		}
		built = true;
	}

	void add(int x, int y) {
		assert(built);
		for (int i = x + 1; i <= n; i += i & -i) {
			for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1; j <= nn[i]; j += j & -j) {
				f[i][j] += 1;
			}
		}
	}

	long long get(int x, int y) {
		assert(built);

		long long res = 0;		
		for (int i = x; i > 0; i -= i & -i) {
			for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin(); j > 0; j -= j & -j) {
				res += f[i][j];
			}
		}
		return res;
	}

	long long get(int x1, int y1, int x2, int y2) {
		return get(x2, y2) - get(x1, y2) - get(x2, y1) + get(x1, y1);
	}

	Fenwick(int n = 0) : n(n), ys(n + 1), f(n + 1), nn(n + 1), built(false) {}
};

int n, m;
int k;
vector<pair<int, int> > a;
Fenwick fv, fex, fey, ff;
int mnx, mny, mxx, mxy;

bool blocked(int x, int y) {
	const auto p = make_pair(x, y);
	auto it = lower_bound(a.begin(), a.end(), p);
	return it != a.end() && *it == p;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R;
	m = C;
	
	int x = sr - 1, y = sc - 1;
	a.emplace_back(x, y);
	for (int i = 0; i < M; ++i) {
		if (S[i] == 'N') {
			--x;
		}
		if (S[i] == 'S') {
			++x;
		}
		if (S[i] == 'E') {
			++y;
		}
		if (S[i] == 'W') {
			--y;
		}

		a.emplace_back(x, y);
	}
	
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());

	mnx = numeric_limits<int>::max();
	mxx = numeric_limits<int>::min();
	mny = numeric_limits<int>::max();
	mxy = numeric_limits<int>::min();

	vector<pair<int, int>> v, ex, ey, f;
	for (const auto &[x, y] : a) {
		mnx = min(mnx, x);
		mxx = max(mxx, x);
		mny = min(mny, y);
		mxy = max(mxy, y);

		v.emplace_back(x, y);
		ex.emplace_back(x, y);
		ey.emplace_back(x, y);
		f.emplace_back(x, y);
		if (x > 0) {
			ex.emplace_back(x - 1, y);
			f.emplace_back(x - 1, y);
		}
		if (y > 0) {
			ey.emplace_back(x, y - 1);
			f.emplace_back(x, y - 1);
		}
		if (x > 0 && y > 0) {
			f.emplace_back(x - 1, y - 1);
		}
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	sort(ex.begin(), ex.end());
	ex.resize(unique(ex.begin(), ex.end()) - ex.begin());
	sort(ey.begin(), ey.end());
	ey.resize(unique(ey.begin(), ey.end()) - ey.begin());
	sort(f.begin(), f.end());
	f.resize(unique(f.begin(), f.end()) - f.begin());

	fv = {n};
	fex = {n};
	fey = {n};
	ff = {n};

	for (const auto &[x, y] : v) {
		fv.fake_add(x, y);
	}
	for (const auto &[x, y] : ex) {
		fex.fake_add(x, y);
	}
	for (const auto &[x, y] : ey) {
		fey.fake_add(x, y);
	}
	for (const auto &[x, y] : f) {
		ff.fake_add(x, y);
	}

	fv.build();
	fex.build();
	fey.build();
	ff.build();

	for (const auto &[x, y] : v) {
		fv.add(x, y);
	}
	for (const auto &[x, y] : ex) {
		fex.add(x, y);
	}
	for (const auto &[x, y] : ey) {
		fey.add(x, y);
	}
	for (const auto &[x, y] : f) {
		ff.add(x, y);
	}
}	

int colour(int ar, int ac, int br, int bc) {
	int x1 = ar - 1, y1 = ac - 1, x2 = br, y2 = bc;
	
	long long v = (long long) (x2 - x1) * (y2 - y1) - fv.get(x1, y1, x2, y2);
	long long e = (long long) (x2 - x1 - 1) * (y2 - y1) - fex.get(x1, y1, x2 - 1, y2) + (long long) (x2 - x1) * (y2 - y1 - 1) - fey.get(x1, y1, x2, y2 - 1);
	long long f = (long long) (x2 - x1 - 1) * (y2 - y1 - 1) - ff.get(x1, y1, x2 - 1, y2 - 1) + (mnx > x1 && mny > y1 && mxx < x2 - 1 && mxy < y2 - 1);
	
	if (v == 0) {
		return 0;
	}

	long long c = f - e + v;
	
	return (int) c;
}

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