Submission #775317

#	Time	Username	Problem	Language	Result	Execution time	Memory
775317		gagik_2007	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	413 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
vector<vector<int>>a;
vector<vector<int>>used;
vector<vector<int>>d;

void init(int R, int C, int sr, int sc, int M, char* SSSSSS) {
    string S=SSSSSS;
    n=R;
    m=C;
    a.resize(n+2, vector<int>(0, 0));
    used.resize(n+2, vector<int>(0, 0));
    d.resize(n+2, vector<int>(0, 0));
    for(int i=0;i<=n+1;i++){
        a[i].resize(m+2, 0);
        used[i].resize(m+2, 0);
        d[i].resize(m+2, 0);
    }
    // cout<<"a: "<<a.size()<<"x"<<a[0].size()<<endl;
    // cout<<a[6][3]<<endl;
    int i=sr,j=sc;
    a[i][j]=1;
    for(int ch:S){
        if(ch=='N'){
            i--;
        }
        if(ch=='E'){
            j++;
        }
        if(ch=='S'){
            i++;
        }
        if(ch=='W'){
            j--;
        }
        a[i][j]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0&&a[i][j+1]==1){
                d[i][j]=d[i][j-1]+1;
            }
            else{
                d[i][j]=d[i][j-1];
            }
        }
    }
}

vector<pii>deltas={make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)};

void dfs(int i, int j, int mxi, int mni, int mxj, int mnj){
    // cout<<"DFS: "<<i<<" "<<j<<endl;
    used[i][j]=1;
    for(pii delta:deltas){
        int di=delta.ff;
        int dj=delta.ss;
        if(i+di<=mxi&&i+di>=mni&&j+dj<=mxj&&j+dj>=mnj){
            // cout<<"STUG: "<<i+di<<" "<<j+dj<<endl;
            if(!used[i+di][j+dj]&&!a[i+di][j+dj]){
                // cout<<"STUG OK"<<endl;
                dfs(i+di,j+dj,mxi,mni,mxj,mnj);
            }
            // cout<<"STUG EXAV"<<endl;
        }
    }
}

int hashvi1(int ac, int bc){
    int cnt=0;
    cnt+=d[1][bc]-d[1][ac-1];
    if(a[1][bc]==0&&a[1][bc+1]==0)cnt++;
    return cnt;
}

int hashvi2(int ac, int bc){
    int cnt=0;
    cnt+=d[2][bc]-d[2][ac-1];
    if(a[2][bc]==0&&a[2][bc+1]==0)cnt++;
    return cnt;
}

int colour(int ar, int ac, int br, int bc) {
    // cout<<"QUERY: "<<ar<<" "<<ac<<" "<<br<<" "<<bc<<endl;
    if(n<=50&&m<=50){
        int cnt=0;
        for(int i=ar;i<=br;i++){
            for(int j=ac;j<=bc;j++){
                if(!used[i][j]&&!a[i][j]){
                    cnt++;
                    dfs(i,j,br,ar,bc,ac);
                }
            }
        }
        for(int i=ar;i<=br;i++){
            for(int j=ac;j<=bc;j++){
                used[i][j]=0;
            }
        }
        return cnt;
    }
    int cnt=0;
    if(ar==1&&br==2){
        cnt=hashvi1(ac,bc);
        cnt+=hashvi2(ac,bc);
        if(a[1][bc]==0&&a[2][bc]==0)cnt--;
        if(a[1][ac]==0&&a[2][ac]==0)cnt--;
        if((d[1][bc]-d[1][ac-1]==0||(d[1][bc]-d[1][ac-1]==1&&d[1][ac]-d[1][ac-1]==1))
        &&(d[2][bc]-d[2][ac-1]==0||(d[2][bc]-d[2][ac-1]==1&&d[2][ac]-d[2][ac-1]==1)))cnt++;
    }
    else if(ar==1){
        cnt=hashvi1(ac,bc);
    }
    else{
        cnt=hashvi2(ac,bc);
    }
    return cnt;
}

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