Submission #202138

#TimeUsernameProblemLanguageResultExecution timeMemory
202138knon0501Land of the Rainbow Gold (APIO17_rainbow)C++14
12 / 100
1774 ms137864 KiB
#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 (stderr)

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);
         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...