oj.uz

Submission #202138

# Submission time Handle Problem Language Result Execution time Memory
202138 2020-02-14T02:19:24 Z knon0501 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1774 ms 137864 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;

int nn;
int r,c;
vector<int> seg[4][MX*4]; ///정점,세로,가로
 ///가로선분

int f(int lef,int rig,int x,int y,int z,int w,int k,int lev){
    if(x>y || lef>y ||x>rig)return 0;
    if(lef>=x && rig<=y){
        return upper_bound(seg[k][lev].begin(),seg[k][lev].end(),w)-lower_bound(seg[k][lev].begin(),seg[k][lev].end(),z);
    }
    int mid=(lef+rig)/2;
    return f(lef,mid,x,y,z,w,k,lev*2)+f(mid+1,rig,x,y,z,w,k,lev*2+1);
}
void upd(int x,int y){
    seg[0][nn+x-1].push_back(y);
}

void upd2(int x,int y){ ///세로 선분
    seg[1][nn+x-1].push_back(y);
}
void upd3(int x,int y){///가로선분
    seg[2][nn+x-1].push_back(y);
}
void upd4(int x,int y){
    seg[3][nn+x-1].push_back(y);
}
int mix,mxx;
int mxy,miy;
void init(int R, int C, int sr, int sc, int M, char *S) {

    r=R+2;
    c=C+2;
    for(nn=1 ; nn<c ; nn*=2);
    int i;

    int y=sr;
    int x=sc;
    upd4(x,y);
    upd(x,y);
    upd(x+1,y);
    upd(x,y+1);
    upd(x+1,y+1);

    upd2(x,y);
    upd2(x+1,y);
    upd3(x,y);
    upd3(x,y+1);
    mix=x;
    mxx=x+1;
    miy=y;
    mxy=y+1;
    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(x,y);
            upd3(x,y+1);
        }
        if(S[i]=='W'){
            x--;
            upd(x,y);
            upd(x,y+1);
            upd2(x,y);
            upd3(x,y);
            upd3(x,y+1);
        }
        if(S[i]=='S'){
            y++;
            upd(x,y+1);
            upd(x+1,y+1);
            upd2(x,y);
            upd2(x+1,y);
            upd3(x,y+1);
        }
        if(S[i]=='N'){
            y--;
            upd(x,y);
            upd(x+1,y);
            upd2(x,y);
            upd2(x+1,y);
            upd3(x,y);
        }
        upd4(x,y);
        mix=min(x,mix);
        mxx=max(mxx,x+1);
        miy=min(miy,y);
        mxy=max(mxy,y+1);
    }
    for(i=1 ; i<=c ; i++){


        for(int j=0 ; j<4 ; j++){
            sort(seg[j][nn+i-1].begin(),seg[j][nn+i-1].end());
           seg[j][nn+i-1].erase(unique(seg[j][nn+i-1].begin(),seg[j][nn+i-1].end()),seg[j][nn+i-1].end());
        }


    }

    for(i=nn-1 ; i>=1 ; i--){
        for(int j=0 ; j<4 ; j++){
            seg[j][i].resize(seg[j][i*2].size()+seg[j][i*2+1].size());
        }
        merge(seg[0][i*2].begin(),seg[0][i*2].end(),seg[0][i*2+1].begin(),seg[0][i*2+1].end(),seg[0][i].begin());
        merge(seg[1][i*2].begin(),seg[1][i*2].end(),seg[1][i*2+1].begin(),seg[1][i*2+1].end(),seg[1][i].begin());
        merge(seg[2][i*2].begin(),seg[2][i*2].end(),seg[2][i*2+1].begin(),seg[2][i*2+1].end(),seg[2][i].begin());
        merge(seg[3][i*2].begin(),seg[3][i*2].end(),seg[3][i*2+1].begin(),seg[3][i*2+1].end(),seg[3][i].begin());
        for(int j=0 ; j<4 ; j++){
            sort(seg[j][i].begin(),seg[j][i].end());
        }
    }
    /*
    for(i=1 ; i<2*nn ; i++){
        cout<<i<<endl;
        for(auto k: seg[0][i])cout<<k<<" ";
        cout<<endl;
    }*/
}

int colour(int ar, int ac, int br, int bc) {

    int A=f(1,nn,ac+1,bc,ar,br,1,1);
    int B=f(1,nn,ac,bc,ar+1,br,2,1);
    int C=f(1,nn,ac+1,bc,ar,ar,0,1)+f(1,nn,ac+1,bc,br+1,br+1,0,1);
    int D=f(1,nn,ac,ac,ar+1,br,0,1)+f(1,nn,bc+1,bc+1,ar+1,br,0,1);
    int E=f(1,nn,ac,ac,ar,ar,0,1)+f(1,nn,ac,ac,br+1,br+1,0,1)+f(1,nn,bc+1,bc+1,ar,ar,0,1)+f(1,nn,bc+1,bc+1,br+1,br+1,0,1);
    int F=f(1,nn,ac+1,bc,ar+1,br,0,1);
    int G=f(1,nn,ac,bc,ar,br,3,1);
    int v=C+D+F+4;
    int e=A+B+C+2+D+2;
   // cout<<A<<" "<<B<<" "<<C<<" "<<D<<" "<<E<<" "<<F<<" "<<G<<endl;
  //  cout<<v<<" "<<e<<endl;
    if(G==0)return 1;
    if(mix>ac && mxx<=bc && miy>ar && mxy<=br)return 1;

    return e-v-G+1;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:133:9: warning: unused variable 'E' [-Wunused-variable]
     int E=f(1,nn,ac,ac,ar,ar,0,1)+f(1,nn,ac,ac,br+1,br+1,0,1)+f(1,nn,bc+1,bc+1,ar,ar,0,1)+f(1,nn,bc+1,bc+1,br+1,br+1,0,1);
         ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 75512 KB Output is correct
2 Correct 55 ms 75640 KB Output is correct
3 Incorrect 54 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 75512 KB Output is correct
2 Correct 50 ms 75512 KB Output is correct
3 Correct 1186 ms 113272 KB Output is correct
4 Correct 1693 ms 137720 KB Output is correct
5 Correct 1636 ms 135800 KB Output is correct
6 Correct 1178 ms 118140 KB Output is correct
7 Correct 1365 ms 117240 KB Output is correct
8 Correct 662 ms 78952 KB Output is correct
9 Correct 1774 ms 137864 KB Output is correct
10 Correct 1680 ms 135416 KB Output is correct
11 Correct 1289 ms 118052 KB Output is correct
12 Correct 626 ms 133880 KB Output is correct
13 Correct 771 ms 137720 KB Output is correct
14 Correct 824 ms 135500 KB Output is correct
15 Correct 761 ms 118156 KB Output is correct
16 Correct 1219 ms 120216 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 75512 KB Output is correct
2 Correct 259 ms 137464 KB Output is correct
3 Correct 283 ms 120816 KB Output is correct
4 Correct 267 ms 126968 KB Output is correct
5 Correct 223 ms 113516 KB Output is correct
6 Correct 121 ms 86904 KB Output is correct
7 Incorrect 155 ms 94968 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 75512 KB Output is correct
2 Correct 55 ms 75640 KB Output is correct
3 Incorrect 54 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 75512 KB Output is correct
2 Correct 55 ms 75640 KB Output is correct
3 Incorrect 54 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -