Submission #401100

#	Time	Username	Problem	Language	Result	Execution time	Memory
401100		A_D	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	1 ms	332 KiB

rainbow

//#include "rainbow.h"

#include <bits/stdc++.h>


/*

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

//*/

#define LL long long

using namespace std;













const int N=3;
const int MM=2e5+1000;
bool a[N][MM];
int pre[3][MM];
int mn[3];
int mx[3];
int v=0;
void init(int R, int C, int sr, int sc, int M, char *S) {
    string s;
    s+=S;
    int x=sr;
    int y=sc;
    a[x][y]=1;
    mn[1]=1e9;
    mn[2]=1e9;
    mx[1]=0;
    mx[2]=0;
    for(auto z:s){
        mn[x]=min(mn[x],y);
        mx[x]=max(mx[x],y);
        if(z=='N'){
            x--;
        }
        if(z=='S'){
            x++;
        }
        if(z=='W'){
            y--;
        }
        if(z=='E'){
            y++;
        }
        mn[x]=min(mn[x],y);
        mx[x]=max(mx[x],y);
        a[x][y]=1;
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            pre[i][j]=pre[i][j-1];
            if(a[i][j-1]==1&&a[i][j]==0)pre[i][j]++;
        }
    }
    if(mn[1]==1e9)v|=1;
    if(mn[2]==1e9)v|=2;
//    for(int i=1;i<=C;i++)cout<<pre[1][i]<<" ";cout<<endl;
//    cout<<mn[1]<<" "<<mn[2]<<" "<<mx[1]<<" "<<mx[2]<<endl;
  //  cout<<v<<endl;
}

int colour(int ar, int ac, int br, int bc) {
    if(v){
        int ret=0,ret2=0;
        for(int i=ar;i<=br;i++){
      //  cout<<ac<<" "<<mn[i]<<" "<<bc<<" "<<mx[i]<<endl;
    //        cout<<i<<" "<<v<<endl;
            if(v&i){
                ret2=1;
            }
            else{
                if(ac<mn[i])ret++;
                if(bc>mx[i])ret++;
            }
        }
        if(ret2)return 1;
        return ret;
    }
    else if(br-ar==0){
        return pre[ar][bc]-pre[ar][ac-1]+(mn[ar] > ac )+(pre[ar][ac] == pre[ar][ac-1] &&a[ar][ac]==0 );
    }
    else{
        int ans=0;
        ans+=pre[1][bc]-pre[1][ac-1]+(pre[1][ac] == pre[1][ac-1] &&a[1][ac]==0  );
  //      cout<<ans<<" ";
        ans+=pre[2][bc]-pre[2][ac-1]+(pre[2][ac] == pre[2][ac-1] &&a[2][ac]==0  );
    //    cout<<ans<<" ";
        int h=-(max(mx[1],mx[2])<bc);
      //  cout<<h<<endl;
        //cout<<(max(mn[1],mn[2])>ac)<<" "<<(max(mx[1],mx[2])<bc)<<endl;
//        cout<<max(mx[1],mx[2])<<" "<<bc<<endl;
        ans+=h;
        return ans;
    }
}



/*


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;
}


//*/


/*

2 12 13 1000
1 2
EEESEEENEESEE


2 8 4 1000
1 2
EEEE

*/

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