Submission #162093

#	Time	Username	Problem	Language	Result	Execution time	Memory
162093		Minnakhmetov	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1987 ms	175568 KiB

rainbow

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

using namespace std;

#define all(aaa) aaa.begin(), aaa.end()

const int N = 2e5 + 5, INF = 1e9;

struct ST {
	vector<pair<int, int>> pts;
	vector<int> t[N * 4];

	void init() {
		if (!pts.empty()) {
			sort(all(pts));
			pts.erase(unique(all(pts)), pts.end());
			build(1, 0, (int)pts.size() - 1);	
		}
	}

	void build(int v, int L, int R) {
		if (L == R) {
			t[v] = {pts[L].second};
		}
		else {
			int m = (L + R) >> 1;
			build(v * 2, L, m);
			build(v * 2 + 1, m + 1, R);
			merge(all(t[v * 2]), all(t[v * 2 + 1]), back_inserter(t[v]));
		}
	}

	int que(int lx, int rx, int ly, int ry, int v, int L, int R) {
		if (rx < pts[L].first || lx > pts[R].first)
			return 0;
		if (lx <= pts[L].first && pts[R].first <= rx) {
			return upper_bound(all(t[v]), ry) - lower_bound(all(t[v]), ly);
		}
		int m = (L + R) >> 1;
		return que(lx, rx, ly, ry, v * 2, L, m)
			+ que(lx, rx, ly, ry, v * 2 + 1, m + 1, R);
	}

	int que(int lx, int rx, int ly, int ry) {
		if (pts.empty())
			return 0;
		return que(lx, rx, ly, ry, 1, 0, pts.size() - 1);
	}

} teh, tev, tf, tv;

string dir = "NSEW";
const int dx[4] = {-1, 1, 0, 0},
		  dy[4] = {0, 0, 1, -1},
		  sdx[4] = {1, 1, 0, 0},
		  sdy[4] = {0, 1, 0, 1};

int r, c;
int mnx, mny, mxx, mxy;
set<pair<int, int>> st;

void init(int R, int C, int sr, int sc, int M, char *S) {
	r = R;
	c = C;

	mnx = sr;
	mxx = sr;
	mny = sc;
	mxy = sc;

	int x = sr, y = sc;
	st.insert({x, y});

	for (int i = 0; i < M; i++) {
		int k = find(all(dir), S[i]) - dir.begin();
		x += dx[k];
		y += dy[k];
		st.insert({x, y});

		mnx = min(mnx, x);
		mxx = max(mxx, x);
		mny = min(mny, y);
		mxy = max(mxy, y);
	}

	for (auto p : st) {
		tf.pts.push_back(p);
		tev.pts.push_back({p.first, p.second});
		tev.pts.push_back({p.first - 1, p.second});
		teh.pts.push_back({p.first, p.second});
		teh.pts.push_back({p.first, p.second - 1});

		for (int i = 0; i < 4; i++) {
			tv.pts.push_back({p.first - sdx[i], p.second - sdy[i]});
		}
	}

	tev.init();
	teh.init();
	tv.init();
	tf.init();
}

int colour(int ar, int ac, int br, int bc) {
	int ans = 1;

	if (ar < mnx && mxx < br &&
		ac < mny && mxy < bc) {
		ans++;
	}

	// ans = 0;
	ans += tev.que(ar, br - 1, ac, bc);
	ans += teh.que(ar, br, ac, bc - 1);
	ans -= tv.que(ar, br - 1, ac, bc - 1);
	ans -= tf.que(ar, br, ac, bc);

	// // count of edges

	// for (int i = ar; i < br; i++) {
	// 	for (int j = ac; j <= bc; j++) {
	// 		ans += (a[i][j] || a[i + 1][j]);
	// 	}
	// }

	// for (int i = ar; i <= br; i++) {
	// 	for (int j = ac; j < bc; j++) {
	// 		ans += (a[i][j + 1] || a[i][j]);
	// 	}
	// }

	// // count of vertices
	// for (int i = ar; i < br; i++) {
	// 	for (int j = ac; j < bc; j++) {
	// 		if (a[i][j] || a[i + 1][j] 
	// 			|| a[i][j + 1] || a[i + 1][j + 1])
	// 			ans--;
	// 	}
	// }

	// // count of useless
	// for (int i = ar; i <= br; i++) {
	// 	for (int j = ac; j <= bc; j++) {
	// 		ans -= a[i][j];
	// 	}
	// }
	
	return ans;
}

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