Submission #183328

#	Time	Username	Problem	Language	Result	Execution time	Memory
183328		oolimry	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1134 ms	99020 KiB

rainbow

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

///Land cells is a vertex, and two adjacent land cells
///All faces formed are 2x2 squares, where all 4 cells are land cells
///Except possibly when the entire rectangle surrounds the rivers, then there is 1 more additonal face on the inside
///No. of components = V - E + F (We ignore the outer face as a face)
///As the V, E and F are large, we instead use a segment tree to count how many vertices, edges and faces are absent. 

const int N = 200002;
int totalRivers;
struct segment{
	vector<int> tree[2*N+5];
	
	inline void update(int i, int v){
		tree[i+N].push_back(v);
	}
	
	inline void getReady(){
		for(int i = N;i < 2*N;i++){
			sort(tree[i].begin(),tree[i].end());
			tree[i].erase(unique(tree[i].begin(),tree[i].end()),tree[i].end());
		}
		for(int i = N-1;i > 0;i--){ ///basically merge sort
			tree[i] = vector<int>(tree[i<<1].size()+tree[i<<1|1].size());
			merge(tree[i<<1].begin(),tree[i<<1].end(), tree[i<<1|1].begin(),tree[i<<1|1].end(),tree[i].begin());
		}
	}
	
	inline int query(int l, int r, int x, int y){ 
		int ans = 0;
		for(l += N, r += (N+1);l < r;l >>= 1, r >>= 1){
			if(l&1){
				ans += upper_bound(tree[l].begin(),tree[l].end(),y) - lower_bound(tree[l].begin(),tree[l].end(),x);
				l++;
			}
			if(r&1){
				r--;
				ans += upper_bound(tree[r].begin(),tree[r].end(),y) - lower_bound(tree[r].begin(),tree[r].end(),x);
			}
		}
		return ans;
	}

} vertices, horizontal, vertical, faces;
///Vertices store vertices which are rivers
///Edges store edges which are not between two land cells, horizontal is (r,c) to (r,c+1), vertical is (r,c) to (r+1,c)
///Squares store which group of 4 sqaures with at least 1 river. It stores the top left corner (r,c)

void addRiver(int r, int c){
	vertices.update(r,c);
	horizontal.update(r,c-1);
	horizontal.update(r,c);
	vertical.update(c,r-1);
	vertical.update(c,r);
	faces.update(r-1,c-1);
	faces.update(r,c-1);
	faces.update(r-1,c);
	faces.update(r,c);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	addRiver(sr,sc);
	for(int i = 0;i < M;i++){
		if(S[i] == 'N') sr--;
		else if(S[i] == 'S') sr++;
		else if(S[i] == 'E') sc++;
		else sc--;
		addRiver(sr,sc);
	}
	vertices.getReady(); horizontal.getReady(); vertical.getReady(); faces.getReady();
	totalRivers = vertices.query(0,N-1,0,N-1);
}

int colour(int T, int L, int B, int R) {
	long long H = B - T + 1, W = R - L + 1;
	
	long long V = H * W - vertices.query(T,B,L,R);
	long long E = (H-1)*W + (W-1)*H - horizontal.query(T,B,L,R-1) - vertical.query(L,R,T,B-1);
	long long F = (H-1)*(W-1) - faces.query(T,B-1,L,R-1);
	if(vertices.query(T+1,B-1,L+1,R-1) == totalRivers) F++;
	
	return V - E + F;
}

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