Submission #1117122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117122		hyakup	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	73 ms	27592 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;


const int maxn = 2e5 + 10;
const int inf = 1e9;

int marc[4][maxn], sum[4][maxn], head[4][maxn];
int n, m, q;

int di[] = { 0, 1, 0, -1 };
int dj[] = { 1, 0, -1, 0 };
int linha1, linha2, coluna1, coluna2;

bool in_bounds( int i, int j ){
    return linha1 <= i && i <= linha2 && coluna1 <= j && j <= coluna2;
}


void dfs( int i, int j ){
    // bug(i);
    // bug(j);
    marc[i][j] = q;
    for( int d = 0; d < 4; d++ ) if( marc[i + di[d]][j + dj[d]] < q && in_bounds( i + di[d], j + dj[d] ) ) dfs( i + di[d], j + dj[d] );
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    // bug(R);
    coluna1 = 1, coluna2 = m;
    marc[sr][sc] = inf;
    for( int i = 0; i < M; i++ ){
        char c = S[i];
        if( c == 'N' ) sr--;
        if( c == 'S' ) sr++;
        if( c == 'W' ) sc--;
        if( c == 'E' ) sc++;

        marc[sr][sc] = inf;
    }

    for( int i = 1; i <= 2; i++ ){
        // cout << "sla " << endl;
        linha1 = linha2 = i;
        for( int j = m; j > 0; j-- ){
            if( !marc[i][j] ){
                q = j;
                dfs( i, j );
            }

        }
        for( int j = 1;j <= m; j++ ){
            sum[i][j] = sum[i][j - 1] + (( marc[i][j] == j ) ? 1 : 0 );
            head[i][j] = marc[i][j];
            if( marc[i][j] != inf ) marc[i][j] = 0;
            // bug(sum[i][j]);
        }
    }

    linha1 = 1; linha2 = 2;
    for( int j = m; j > 0; j-- ) for( int i = 1;i <= 2; i++ ){
        if( !marc[i][j] ){
            q = j;
            dfs( i, j );
        }
    }

    for( int j = 1; j <= m; j++ ){
        sum[3][j] = sum[3][j - 1] + (( marc[1][j] == j || marc[2][j] == j ) ? 1 : 0 );
        if( marc[1][j] != inf ) head[3][j] = marc[1][j];
        else head[3][j] = marc[2][j];
        // bug(sum[3][j]);
    }

}



int colour(int ar, int ac, int br, int bc) {
    int id = (( ar < br ) ? 3 : ar );

    int resp = sum[id][bc] - sum[id][ac - 1];
    if( head[id][bc] > bc && head[id][bc] != inf ) resp++;
    return resp;
}

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