#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
178 ms |
61176 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
