제출 #202113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202113		knon0501	무지개나라 (APIO17_rainbow)	C++14	0 / 100	178 ms	61176 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;
int root1[MX];
int root2[MX];
int root3[MX];
int root4[MX];
int nn;
int r,c;
int vcnt,ecnt;
struct Node{
    int lef,rig,val;
}seg[MX*100];
int m;
void f(int lef,int rig,int k,int lev){
    if(lef==rig){
        seg[lev].val=1;
        return;
    }
    int mid=(lef+rig)/2;
    if(k<=mid){
        if(!seg[lev].lef)seg[lev].lef=++nn;
        f(lef,mid,k,seg[lev].lef);
    }
    if(k>mid){
        if(!seg[lev].rig)seg[lev].rig=++nn;
        f(mid+1,rig,k,seg[lev].rig);
    }
    seg[lev].val=seg[seg[lev].lef].val+seg[seg[lev].rig].val;
}
int g(int lef,int rig,int x,int y,int lev){

    if(lev==0 || x>rig || lef>y || x>y)return 0;
    if(lef>=x && rig<=y)return seg[lev].val;
    int mid=(lef+rig)/2;
    return g(lef,mid,x,y,seg[lev].lef)+g(mid+1,rig,x,y,seg[lev].rig);
}
void upd(int x,int y){
    if(root1[x]==0)root1[x]=++nn;
    if(root2[y]==0)root2[y]=++nn;
    f(1,r,y,root1[x]);
    f(1,c,x,root2[y]);
}
int mxx;
int mix;
int mxy;
int miy;
void upd2(int x,int y){ ///세로 선분
    if(root3[x]==0)root3[x]=++nn;
    f(1,r,y,root3[x]);
}
void upd3(int y,int x){///가로선분
    if(root4[y]==0)root4[y]=++nn;
    f(1,c,x,root4[y]);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
    r=R+2;
    c=C+2;
    m=M+1;
    upd(sr,sc);
    upd(sr+1,sc);
    upd(sr,sc+1);
    upd(sr+1,sc+1);
    upd2(sc,sr);
    upd2(sc+1,sr);
    upd3(sr,sc);
    upd3(sr+1,sc);


    int i;
    int y=sr;
    int x=sc;
    mxx=sc+1;
    mix=sc;
    mxy=sr+1;
    miy=sr;
    set<pair<int,int>> St;
    St.insert({x,y});
    for(i=0 ; i<M ; i++){
        if(S[i]=='E'){
            x++;
            upd(x+1,y);
            upd(x+1,y+1);
            upd2(x+1,y);
            upd3(y,x);
            upd3(y+1,x);
        }
        if(S[i]=='W'){
            x--;
            upd(x,y);
            upd(x,y+1);
            upd2(x,y);
            upd3(y,x);
            upd3(y+1,x);
        }
        if(S[i]=='S'){
            y++;
            upd(x,y+1);
            upd(x+1,y+1);
            upd2(x,y);
            upd2(x+1,y);
            upd3(y+1,x);
        }
        if(S[i]=='N'){
            y--;
            upd(x,y);
            upd(x+1,y);
            upd2(x,y);
            upd2(x+1,y);
            upd3(y,x);
        }
        mxx=max(mxx,x+1);
        mix=min(mix,x);
        mxy=max(mxy,y+1);
        miy=min(miy,y);
        St.insert({x,y});
    }
    m=St.size();
    for(i=1 ; i<=c ; i++)vcnt+=seg[root1[i]].val;
    for(i=1 ; i<=c  ; i++)ecnt+=seg[root3[i]].val;
    for(i=1 ; i<=r ; i++)ecnt+=seg[root4[i]].val;
}

int colour(int ar, int ac, int br, int bc) {
    if(mxx<ac || mix>bc || mxy<ar ||miy>br)return 1;
    int V=vcnt+4;
    int E=ecnt;
    br++;
    bc++;
   /// cout<<E<<" "<<V<<endl;
    V-=g(1,r,ar,ar,root1[ac])+g(1,r,br,br,root1[bc])+g(1,r,ar,ar,root1[bc])+g(1,r,br,br,root1[ac]);
    E+=g(1,r,ar+1,br-1,root1[ac])+1-g(1,r,ar,br-1,root3[ac]);
    E+=g(1,r,ar+1,br-1,root1[bc])+1-g(1,r,ar,br-1,root3[bc]);
    E+=g(1,c,ac+1,bc-1,root2[ar])+1-g(1,c,ac,bc-1,root4[ar]);
    E+=g(1,c,ac+1,bc-1,root2[br])+1-g(1,c,ac,bc-1,root4[br]);
   /// cout<<E<<" "<<V<<endl;
    return 1+E-V-m;
}

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