Submission #169259

#	Time	Username	Problem	Language	Result	Execution time	Memory
169259		mohammad_kilani	Land of the Rainbow Gold (APIO17_rainbow)	C++17	35 / 100	2252 ms	15968 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector< int > arr[N];

int n , m;

int cnt = 0 , dsu[N << 1];

int Find(int u){
	return (u == dsu[u] ? u : dsu[u] = Find(dsu[u]));
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R,  m = C;
	arr[sr].push_back(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--;
		arr[sr].push_back(sc);
	}
	for(int i = 1;i <= R;i++){
		sort(arr[i].begin(),arr[i].end());
		arr[i].resize(unique(arr[i].begin(),arr[i].end()) - arr[i].begin());
	}
}

vector < pair<int,int> > cur , pre;


int colour(int ar, int ac, int br, int bc) {
	int ans = 0 , a , b, j;
	cur.clear();
	pre.clear();
	for(int i = ar ;i <= br;i++){
		j = lower_bound(arr[i].begin(),arr[i].end(), ac) - arr[i].begin();
		a = ac - 1;
		while(j < (int)arr[i].size() && arr[i][j] <= bc){
			if(a + 1 <= arr[i][j] - 1){
				cur.push_back(make_pair(a + 1 , arr[i][j] - 1));
			}
			a = arr[i][j];
			j++;
		}
		if(a + 1 <= bc) cur.push_back(make_pair(a + 1,  bc));
		ans += (int)cur.size();
		for(j = 0 ;j < (int)cur.size();j++){
			dsu[cnt + j] = cnt + j;
		}
		j = 0;
		for(int i = 0;i < (int)cur.size();i++){
			while(j < (int)pre.size() && pre[j].second < cur[i].first) j++;
			while(j < (int)pre.size() && pre[j].first <= cur[i].second){
				a = Find(cnt - (int)pre.size() + j);
				b = Find(cnt + i);
				if(a != b){
					ans--;
					dsu[a] = b;
				}
				j++;
			}
			if(j)
				j--;
		}
		cnt += (int)cur.size();
		swap(pre , cur);
		cur.clear();
	}
    return ans;
}

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