#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;
int nn;
int r,c;
int vcnt,ecnt;
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++){
sort(seg[0][nn+i-1].begin(),seg[0][nn+i-1].end());
sort(seg[1][nn+i-1].begin(),seg[1][nn+i-1].end());
sort(seg[2][nn+i-1].begin(),seg[2][nn+i-1].end());
sort(seg[3][nn+i-1].begin(),seg[3][nn+i-1].end());
unique(seg[0][nn+i-1].begin(),seg[0][nn+i-1].end());
unique(seg[1][nn+i-1].begin(),seg[1][nn+i-1].end());
unique(seg[2][nn+i-1].begin(),seg[2][nn+i-1].end());
unique(seg[3][nn+i-1].begin(),seg[3][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());
}
}
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,br,0,1)+f(1,nn,bc+1,bc+1,ar,ar,0,1)+f(1,nn,bc+1,bc+1,br,br,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:130:9: warning: unused variable 'E' [-Wunused-variable]
int E=f(1,nn,ac,ac,ar,ar,0,1)+f(1,nn,ac,ac,br,br,0,1)+f(1,nn,bc+1,bc+1,ar,ar,0,1)+f(1,nn,bc+1,bc+1,br,br,0,1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
75512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
75512 KB |
Output is correct |
| 2 |
Correct |
53 ms |
75512 KB |
Output is correct |
| 3 |
Correct |
1134 ms |
113248 KB |
Output is correct |
| 4 |
Incorrect |
1654 ms |
137640 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
75512 KB |
Output is correct |
| 2 |
Correct |
199 ms |
137540 KB |
Output is correct |
| 3 |
Correct |
114 ms |
120536 KB |
Output is correct |
| 4 |
Correct |
152 ms |
126968 KB |
Output is correct |
| 5 |
Incorrect |
133 ms |
118892 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
75512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
75512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
