Submission #57366

#	Time	Username	Problem	Language	Result	Execution time	Memory
57366		gabrielsimoes	무지개나라 (APIO17_rainbow)	C++17	0 / 100	8 ms	868 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] = 10000000;
                mx[r][c][0] = -10000000;
            }
        }
    }

    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]);
                }
            }
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    int a = 10000000, b = -10000000;

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

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

    return max(b - a, 0);
}

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