Submission #403016

#	Time	Username	Problem	Language	Result	Execution time	Memory
403016		teehandsome	Land of the Rainbow Gold (APIO17_rainbow)	C++11	12 / 100	234 ms	16452 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=2e5+10;
bool flag[2][mxn];
int dm[4]={-1,0,1,0};
int dn[4]={0,1,0,-1};
char dir[4]={'N','E','S','W'};

struct dt {
    int cnt; bool ul,dl,ur,dr;
};

dt t[3][3*mxn];

dt unite(dt l,dt r) {
    dt res;
    res.cnt=l.cnt+r.cnt;
    res.ul=l.ul; res.dl=l.dl;
    res.ur=r.ur; res.dr=r.dr;
    if(l.cnt and r.cnt) {
        if((!l.ur and !r.ul) or (!l.dr and !r.dl)) res.cnt--;
    }
    return res;
}

void build(int v,int tl,int tr) {
    if(tl>tr) return;
    if(tl==tr) {
        if(flag[0][tl] and flag[1][tl]) {
            t[2][v]={0,true,true,true,true};
        }
        else {
            t[2][v]={1,flag[0][tl],flag[1][tl],flag[0][tl],flag[1][tl]};
        }
        return;
    }
    int mid=(tl+tr)/2;
    build(2*v,tl,mid);  build(2*v+1,mid+1,tr);
    t[2][v]=unite(t[2][2*v],t[2][2*v+1]);
}
void debugdt(dt x) {
    cout<<"#"<<": "<<x.cnt<<endl;
}
dt query(int idx,int v,int tl,int tr,int l,int r) {
    if(tl>tr or tl>r or tr<l) return {0,1,1,1,1};
    if(tl>=l and tr<=r) return t[idx][v];
    int mid=(tl+tr)/2;
    dt L=query(idx,2*v,tl,mid,l,r);
    dt R=query(idx,2*v+1,mid+1,tr,l,r);
    dt res=unite(L,R);
//    debug(L.cnt,R.cnt,res.cnt);
    return unite(L,R);
}

int r,c;

void build2(int idx,int v,int tl,int tr) {
    if(tl>tr) return;
    if(tl==tr) {
        if(flag[idx][tl]) t[idx][v]={0,1,1,1,1};
        else t[idx][v]={1,0,0,0,0};
    }
    else {
        int mid=(tl+tr)/2;
        build2(idx,2*v,tl,mid);
        build2(idx,2*v+1,mid+1,tr);
        t[idx][v]=unite(t[idx][2*v],t[idx][2*v+1]);
    }
}

void deebug(int idx,int v,int tl,int tr) {
    if(tl>tr) return;
    cout<<"# {"<<tl<<" "<<tr<<"}"<<": "<<t[idx][v].cnt<<endl;
    if(tl==tr) return;
    int mid=(tl+tr)/2;
    deebug(idx,2*v,tl,mid);
    deebug(idx,2*v+1,mid+1,tr);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    r=R,c=C;
    --sr; --sc;
    flag[sr][sc]=true;
    for(int i=0;i<M;i++) {
        for(int j=0;j<4;j++) {
            if(S[i]==dir[j]) {
                sr+=dm[j]; sc+=dn[j]; break;
            }
        }
        flag[sr][sc]=true;
    }
//    for(int i=0;i<R;i++) {
//        for(int j=0;j<C;j++) {
//            cout<<flag[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    build(1,0,C-1);
    for(int i=0;i<2;i++) {
        build2(i,1,0,C-1);
    }
//    deebug(1,1,0,c-1);

}


int colour(int ar, int ac, int br, int bc) {
    dt ans;
    --ar; --ac; --br; --bc;
    if(ar==br) {
        ans=query(ar,1,0,c-1,ac,bc);
    }
    else {
        ans=query(2,1,0,c-1,ac,bc);
    }
    return ans.cnt;
}

Compilation message (stderr)

rainbow.cpp: In function 'dt query(int, int, int, int, int, int)':
rainbow.cpp:80:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   80 |     dt res=unite(L,R);
      |        ^~~

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