| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 57358 | gabrielsimoes | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int R, C;
bitset<MAX> land[MAX];
int sum[3][MAXN];
// int color[3][MAXN], _color = 0;
// void dfs_1(int r, int c, int ar, int ac, int br, int bc) {
// for (int d = 0; d < 4; d++) {
// int nr = r + dr[d], nc = c + dc[d];
// if (r >= ar && r <= br && c >= ac && c <= bc && land[nr][nc] && color[nr][nc] == 0) {
// color[nr][nc] = color[r][c];
// dfs_1(nr, nc, ar, ac, br, bc);
// }
// }
// }
void init(int _R, int _C, int sr, int sc, int M, char *S) {
R = _R; C = _C;
for (int r = 1; r <= R; r++)
for (int c = 1; c <= C; c++)
land[r][c] = true;
land[sr][sc] = false;
for (int i = 0; i < M; i++) {
int d = 0;
switch(S[i]) {
case 'N': d = 0; break;
case 'E': d = 1; break;
case 'S': d = 2; break;
case 'W': d = 3; break;
}
sr += dr[d];
sc += dc[d];
land[sr][sc] = false;
}
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
if (land[r][c+1]) {
sum[r][c] = sum[r][c-1] + 1;
} else {
sum[r][c] = sum[r][c-1];
}
}
}
}
int colour(int ar, int ac, int br, int bc) {
int ret = 0;
for (int r = ar; r <= br; r++) {
ret += sum[r][bc] - sum[r][ac-1] + (land[r][bc] ? 0 : 1);
}
}
