Submission #57372

#	Time	Username	Problem	Language	Result	Execution time	Memory
57372		gabrielsimoes	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	9 ms	988 KiB

rainbow

#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<MAXN> land[3];
int color[3][MAXN], _color = 0;
int mn[3][MAXN][20];
int mx[3][MAXN][20];

void dfs(int r, int c) {
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (land[nr][nc] && color[nr][nc] == 0) {
            color[nr][nc] = color[r][c];
            dfs(nr, nc);
        }
    }
}

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] && color[r][c] == 0) {
                color[r][c] = ++_color;
                dfs(r, c);
            }

            if (land[r][c]) {
                mn[r][c][0] = color[r][c];
                mx[r][c][0] = color[r][c];
            } else {
                mn[r][c][0] = 3 * MAXN;
                mx[r][c][0] = -3 * MAXN;
            }
        }
    }

    for (int i = 1; i < 20; i++) {
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                if (c + (1 << i) - 1 <= C) {
                    mn[r][c][i] = min(mn[r][c][i-1], mn[r][c + (1 << (i-1)) - 1][i-1]);
                    mx[r][c][i] = max(mx[r][c][i-1], mx[r][c + (1 << (i-1)) - 1][i-1]);
                }
            }
        }
    }

    // for (int i = 0; i <= 3; i++) {
    //     for (int r = 1; r <= R; r++) {
    //         for (int c = 1; c <= C; c++) {
    //             if (c + (1 << i) - 1 <= C) {
    //                 printf("r %d c %d i %d (1 << i) %d mn %d mx %d\n", r, c, i, (1 << i), mn[r][c][i], mx[r][c][i]);
    //             }
    //         }
    //     }
    // }

    // for (int r = 1; r <= R; r++) {
    //     for (int c = 1; c <= C; c++) {
    //         printf("%d ", color[r][c]);
    //     }
    //     printf("\n");
    // }
}

int colour(int ar, int ac, int br, int bc) {
    int a = 3*MAXN, b = -3 * MAXN;

    int x = 20;
    while ((1 << x) > (bc - ac + 1)) x--;

    // printf("x == %d\n", x);
    // printf("looking at %d->%d and %d->%d\n", ac, ac + (1 << x)-1, bc - (1 << x) + 1, bc - (1 << x) + 1 + (1 << x) - 1);

    for (int r = ar; r <= br; r++) {
        for (int c = ac; c <= bc; c++) {
            a = min(a, mn[r][c][0]);
            b = max(b, mx[r][c][0]);
        }
        // a = min(a, min(mn[r][ac][x], mn[r][bc - (1 << x) + 1][x]));
        // b = max(b, max(mx[r][ac][x], mx[r][bc - (1 << x) + 1][x]));
    }

    // printf("%d %d\n", a, b);

    return max(b - a + 1, 0);
}

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