oj.uz

Submission #202137

# Submission time Handle Problem Language Result Execution time Memory
202137 2020-02-14T02:04:21 Z knon0501 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1801 ms 140632 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(x,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 54 ms 75512 KB Output is correct
2 Correct 59 ms 75732 KB Output is correct
3 Incorrect 55 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 51 ms 75512 KB Output is correct
3 Correct 1184 ms 113400 KB Output is correct
4 Correct 1697 ms 137720 KB Output is correct
5 Correct 1694 ms 138360 KB Output is correct
6 Correct 1199 ms 121080 KB Output is correct
7 Correct 1365 ms 120184 KB Output is correct
8 Correct 670 ms 81900 KB Output is correct
9 Correct 1801 ms 140632 KB Output is correct
10 Correct 1701 ms 138208 KB Output is correct
11 Correct 1296 ms 121084 KB Output is correct
12 Correct 653 ms 136824 KB Output is correct
13 Correct 766 ms 140536 KB Output is correct
14 Correct 797 ms 138232 KB Output is correct
15 Correct 746 ms 120952 KB Output is correct
16 Correct 1226 ms 123000 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 75512 KB Output is correct
2 Correct 262 ms 137464 KB Output is correct
3 Correct 286 ms 120536 KB Output is correct
4 Correct 263 ms 127096 KB Output is correct
5 Correct 220 ms 113520 KB Output is correct
6 Correct 127 ms 86904 KB Output is correct
7 Incorrect 154 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 54 ms 75512 KB Output is correct
2 Correct 59 ms 75732 KB Output is correct
3 Incorrect 55 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 54 ms 75512 KB Output is correct
2 Correct 59 ms 75732 KB Output is correct
3 Incorrect 55 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -