oj.uz

Submission #57366

# Submission time Handle Problem Language Result Execution time Memory
57366 2018-07-14T16:25:53 Z gabrielsimoes Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 8 ms 868 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 580 KB Output is correct
2 Runtime error 8 ms 868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -