Submission #54803

#	Time	Username	Problem	Language	Result	Execution time	Memory
54803		top34051	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3 ms	668 KiB

rainbow

//Subtask 2

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

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;

int n,m,k;
int a[3][maxn];
map<int,pii> itv[5];

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R; m = C; k = M;
	int x = sr, y = sc;
	a[x][y] = 1;
	for(int i=0;i<k;i++) {
		if(S[i]=='N') x--;
		if(S[i]=='E') y++;
		if(S[i]=='W') y--;
		if(S[i]=='S') x++;
		a[x][y] = 1;
	}
	int sz;
	sz = 0;
	for(int y=1;y<=m;y++) {
		if(!a[1][y]) continue;
		int pos = y;
		while(y+1<=m && a[1][y+1]) y++;
//		printf("1 [%d, %d]\n",pos,y);
		itv[1][y] = {pos,++sz};
	}
	itv[1][m+1] = {m+1, ++sz};
	sz = 0;
	for(int y=1;y<=m;y++) {
		if(!a[2][y]) continue;
		int pos = y;
		while(y+1<=m && a[2][y+1]) y++;
//		printf("2 [%d, %d]\n",pos,y);
		itv[2][y] = {pos,++sz};
	}
    itv[2][m+1] = {m+1,++sz};
	sz = 0;
	for(int y=1;y<=m;y++) {
		if(!a[1][y] && !a[2][y]) continue;
		int pos = y;
		while(y+1<=m && ((a[1][y]&&a[1][y+1]) || (a[2][y]&&a[2][y+1]))) y++;
//		printf("3 [%d, %d]\n",pos,y);
		itv[3][y] = {pos,++sz};
	}
	itv[3][m+1] = {m+1,++sz};
}

int colour(int ar, int ac, int br, int bc) {
    int t;
    if(ar==1 && br==1) t = 1;
    else if(ar==2 && br==2) t = 2;
    else t = 3;
    auto it1 = itv[t].lower_bound(ac);
    auto it2 = itv[t].lower_bound(bc);
    if(it2->Y.X > bc) it2--;
    return it2->Y.Y - it1->Y.Y + 1;
}

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