Submission #524214

#	Time	Username	Problem	Language	Result	Execution time	Memory
524214		sidon	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	921 ms	112564 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define all(X) begin(X), end(X)
 
const int Z = 2e5+4;
 
template<const int n>
struct SegmentTree {
	vector<int> a[2*n];
	void insert(int i, int v) {
		a[i+n].push_back(v);
	}
	void build() {
		for(int i = n; i < 2*n; ++i) {
			sort(all(a[i]));
			a[i].erase(unique(all(a[i])), end(a[i]));
		}
		for(int i = n; --i; )
			merge(all(a[2*i]), all(a[2*i+1]), back_inserter(a[i]));
	}
	int getCnt(int i, int lv, int rv) {
		return upper_bound(all(a[i]), rv) - lower_bound(all(a[i]), lv);
	}
	int count(int l, int r, int lv, int rv) {
		int x = 0;
		for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if(l & 1) x += getCnt(l++, lv, rv);
			if(r & 1) x += getCnt(--r, lv, rv);
		}
		return x;
	}
};
 
SegmentTree<2*Z> edges;
SegmentTree<Z> cells, vertices;
int minR = Z, minC = Z, maxR, maxC;
 
void init(int R, int C, int uR, int uC, int M, char* S) {
	for(int i = 0; i <= M; ++i) {
		cells.insert(uC, uR);
		minR = min(minR, uR);
		minC = min(minC, uC);
		maxR = max(maxR, uR);
		maxC = max(maxC, uC);
		for(int x : {0, 1}) for(int y : {0, 1}) {
			vertices.insert(uC+x, uR+y);
		}
		for(int x : {0, 2}) {
			edges.insert(2*uC+x, 2*uR+1);
			edges.insert(2*uC+1, 2*uR+x);
		}
		if(i < M) {
			S[i] == 'S' ? ++uR : 0;
			S[i] == 'N' ? --uR : 0;
			S[i] == 'E' ? ++uC : 0;
			S[i] == 'W' ? --uC : 0;
		}
	}
	edges.build();
	cells.build();
	vertices.build();
}
 
int colour(int ar, int ac, int br, int bc) {
	bool add = ar < minR && ac < minC && br > maxR && bc > maxC;
	return edges.count(2*ac+1, 2*bc+1, 2*ar+1, 2*br+1) - vertices.count(ac+1, bc, ar+1, br) - cells.count(ac, bc, ar, br) + 1 + add;
}

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