Submission #733427

#	Time	Username	Problem	Language	Result	Execution time	Memory
733427		1075508020060209tc	Land of the Rainbow Gold (APIO17_rainbow)	C++14	12 / 100	144 ms	15812 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
int n;int m;int sx;int sy;
string s;
int gr[5][200005];

struct SGTR{
int l;int r;
int gp[3];
}tr[800005];

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].gp[0]=0;
    tr[nw].gp[1]=0;
    tr[nw].gp[2]=0;
    if(gr[1][l]||gr[2][l]){
        tr[nw].gp[0]=1;
    }
    if(gr[1][l]){
        tr[nw].gp[1]=1;
    }
    if(gr[2][l]){
        tr[nw].gp[2]=1;
    }
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
tr[nw].gp[0]=tr[nw*2].gp[0]+tr[nw*2+1].gp[0];
tr[nw].gp[1]=tr[nw*2].gp[1]+tr[nw*2+1].gp[1];
tr[nw].gp[2]=tr[nw*2].gp[2]+tr[nw*2+1].gp[2];
if((gr[1][mi]&&gr[1][mi+1])||(gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[0]--;
}
if((gr[2][mi]&&gr[2][mi+1])){
    tr[nw].gp[2]--;
}
if((gr[1][mi]&&gr[1][mi+1])){
    tr[nw].gp[1]--;
}
}



void init(int R, int C, int sr, int sc, int M, char *S) {
n=R;m=C;
gr[sr][sc]=1;
for(int i=0;i<M;i++){
    if(S[i]=='N'){sr--;}
    if(S[i]=='S'){sr++;}
    if(S[i]=='W'){sc--;}
    if(S[i]=='E'){sc++;}
    gr[sr][sc]=1;
}
for(int i=1;i<=C;i++){
    gr[1][i]^=1;
    gr[2][i]^=1;
}
buildtr(1,1,C);
}

int ans;int vs;

void slv(int pl,int id){
if(id==0){
    if( (gr[1][pl-1]&&gr[1][pl])||(gr[2][pl-1]&&gr[2][pl])  ){
        ans--;
    }
    return;
}
    if( (gr[id][pl-1]&&gr[id][pl])  ){
        ans--;
    }

}

void qry(int nw,int l,int r,int id){
if(tr[nw].l>=l&&tr[nw].r<=r){
    ans+=tr[nw].gp[id];
    if(vs){slv(tr[nw].l,id);}
    vs=1;
    return;
}
if(tr[nw].l>r||tr[nw].r<l){
    return;
}
qry(nw*2,l,r,id);qry(nw*2+1,l,r,id);
}



int colour(int ar, int ac, int br, int bc) {
ans=0;vs=0;
if(ar==1&&br==2){
    qry(1,ac,bc,0);
    return ans;
}
qry(1,ac,bc,ar);
return ans;
}

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