Submission #547337

#	Time	Username	Problem	Language	Result	Execution time	Memory
547337		Victor	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	77 ms	18500 KiB

rainbow

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

#include "rainbow.h"

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
int rows, cols, AR, AC, BR, BC,min_col,max_col;
bool yes=0;
vii segments[3];
vector<vector<bool>> grid, vis;

bool valid(int row, int col) { return AR <= row && row < BR && AC <= col && col < BC; }

void dfs(int row, int col) {
    vis[row][col] = 1;
    if(yes) {
        min_col=min(min_col,col);
        max_col=max(max_col,col);
    }
    // cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl;
    rep(k, 0, 4) {
        int nr = row + dr[k], nc = col + dc[k];
        if (valid(nr, nc) && !vis[nr][nc] && !grid[nr][nc]) dfs(nr, nc);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    rows = R;
    cols = C;
    --sr;
    --sc;

    rep(i, 0, M) {
        if (S[i] == 'S') S[i] = 0;
        if (S[i] == 'N') S[i] = 1;
        if (S[i] == 'E') S[i] = 2;
        if (S[i] == 'W') S[i] = 3;
    }

    if ((rows <= 50 && cols <= 50) || rows == 2) {
        grid.assign(R, vector<bool>(C, 0));
        grid[sr][sc] = 1;

        rep(i, 0, M) {
            sr += dr[S[i]];
            sc += dc[S[i]];
            grid[sr][sc] = 1;
        }

        //rep(i,0,rows) {
        //     rep(j,0,cols) cout<<grid[i][j]<<' ';
        //     cout<<endl;
        // }
        // cout<<endl;
    }

    if (rows == 2) {
        yes=1;
        AC=0;
        BC=cols;
        rep(k, 0, 3) {
            segments[k].emplace_back(-1,-1);
            if(!k) {
                AR=0;
                BR=1;
            }
            if(k==1) {
                AR=1;
                BR=2;
            }
            if(k==2) {
                AR=0;
                BR=2;
            }

            vis.assign(rows, vector<bool>(cols, 0));
            rep(i, AR, BR) {
                rep(j, 0, cols) {
                    if (vis[i][j] || grid[i][j]) continue;
                    min_col=INF;
                    max_col=0;
                    dfs(i, j);
                    segments[k].emplace_back(min_col,max_col);
                }
            }
        }
        yes=0;
    }
}

int colour(int ar, int ac, int br, int bc) {
    int ans = 0;
    --ar;
    --ac;
    if (rows <= 50 && cols <= 50) {
        AR = ar;
        AC = ac;
        BR = br;
        BC = bc;

        vis.assign(rows, vector<bool>(cols, 0));
        rep(i, ar, br) {
            rep(j, ac, bc) {
                if (vis[i][j] || grid[i][j]) continue;
                ++ans;
                dfs(i, j);
            }
        }
    }

    else if(rows==2) {
        int k=0;
        if(br==2) k=2-ar;
        auto it_left=upper_bound(all(segments[k]),ii(ac,INF));
        if(it_left!=segments[k].begin()) {
            --it_left;
            //cout<<"it_left = "<<it_left->second<<" ac = "<<ac<<endl;
            if(it_left->second<ac) ++it_left;
        }

        //debug(k);
        //debug(sz(segments[k]));
        auto it_right=upper_bound(all(segments[k]),ii(bc,-1));
        --it_right;
        //cout<<"it_right = "<<it_right->first<<' '<<it_right->second<<endl;
        int lpos=it_left-segments[k].begin();
        int rpos=it_right-segments[k].begin();
        ans=max(0,rpos-lpos+1);
        //cout<<lpos<<' '<<rpos<<endl;
    }

    return ans;
}
/*
#include <stdio.h>

#include "rainbow.h"

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}
*/

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:75:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             sr += dr[S[i]];
      |                      ~~~^
rainbow.cpp:76:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |             sc += dc[S[i]];
      |                      ~~~^

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