Submission #1117369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117369		hyakup	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3047 ms	81100 KiB

rainbow

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

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

map<int, map<int, int>> marc;
int n, m, q;


set<pii> proibidos;
vector<pii> todos;
vector<int> linha[maxn], coluna[maxn];

struct Rectangle{
    int i1, j1, i2, j2; Rectangle( int i1, int j1, int i2, int j2 ) : i1(i1), j1(j1), i2(i2), j2(j2) {}
    bool contem( pii ponto ){ return i1 <= ponto.first && ponto.first <= i2 && j1 <= ponto.second && ponto.second <= j2;  }
};

bool find( set<pii>& s, pii p ){ return s.find(p) != s.end(); }

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    Rectangle grid( 1, 1, R, C );
    proibidos.insert({ sr, sc });
    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++;

        proibidos.insert({ sr, sc });
        linha[sr].push_back(sc);
        coluna[sc].push_back(sr);
    }

    for( auto [i, j] : proibidos ){
        for( int di = -1; di <= 1; di ++ ){
            for( int dj = -1; dj <= 1; dj++ ){
                pii novo( i + di, j + dj );
                if( !find(proibidos, novo) && grid.contem(novo) ){
                    linha[novo.first].push_back(novo.second);
                    coluna[novo.second].push_back(novo.first);
                    todos.push_back(novo);
                }

            }
        }
    }
}

void dfs( int i, int j, Rectangle grid ){
    marc[i][j] = q;

    int pos_j = lower_bound( linha[i].begin(), linha[i].end(), j ) - linha[i].begin();
    int pos_i = lower_bound( coluna[j].begin(), coluna[j].end(), i ) - coluna[j].begin();

    int di[] = { -1, 0, 1, 0 };
    int dj[] = { 0, 1, 0, -1 };

    for( int d = 0; d < 4; d++ ){
        int vi = coluna[j][pos_i + di[d]], vj = linha[i][pos_j + dj[d]];
        if( marc[vi][vj] != q && grid.contem(pii(vi, vj)) && !find( proibidos, pii( vi, vj ) ) ) dfs( vi, vj, grid );
    }
}

int colour(int ar, int ac, int br, int bc) {
    Rectangle grid( ar, ac, br, bc );

    q++;

    for( int i = ar; i <= br; i++ ){
        todos.push_back(pii( i, ac ));
        todos.push_back(pii( i, bc ));
        linha[i].push_back(ac);
        linha[i].push_back(bc);
    }

    for( int i = ac; i <= bc; i++ ){
        todos.push_back(pii( ar, i ));
        todos.push_back(pii( br, i ));
        coluna[i].push_back(ar);
        coluna[i].push_back(br);
    }

    for( int i = 1; i <= n; i++ ){
        linha[i].push_back(0); linha[i].push_back(m + 1);
        sort( linha[i].begin(), linha[i].end() );
        linha[i].erase( unique( linha[i].begin(), linha[i].end() ), linha[i].end() );
    }

    for( int i = 1; i <= m; i++ ){
        coluna[i].push_back(0); coluna[i].push_back(n + 1);
        sort( coluna[i].begin(), coluna[i].end() );
        coluna[i].erase( unique( coluna[i].begin(), coluna[i].end() ), coluna[i].end() );
    }

    sort( todos.begin(), todos.end() );
    todos.erase( unique( todos.begin(), todos.end() ), todos.end() );

    int resp = 0;

    for( auto [i, j] : todos ){
        if( grid.contem( pii( i, j ) ) && marc[i][j] != q && !find( proibidos, pii( i, j ) ) ){ resp++; dfs( i, j, grid ); }
    }
    return resp;
}

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