#include<bits/stdc++.h>
#include "rainbow.h"
#define MAXN 200007
using namespace std;
const int maxs=2e5+7;
struct ST{
struct node{
int l,r;
int val;
};
vector<node> tree;
int num;
void init(){
tree.push_back({0,0,0});
tree.push_back({0,0,0});
num=1;
}
void addnode(){
tree.push_back({0,0,0});
num++;
}
void update(int v,int l,int r,int pos){
if(l==r){
tree[v].val++;
}else{
int tt=(l+r)/2;
if(tree[v].l==0){
addnode(); tree[v].l=num;
}
if(tree[v].r==0){
addnode(); tree[v].r=num;
}
if(pos<=tt)update(tree[v].l,l,tt,pos);
else update(tree[v].r,tt+1,r,pos);
tree[v].val=tree[tree[v].l].val+tree[tree[v].r].val;
}
}
int getsum(int v,int l,int r,int ll,int rr){
if(ll>rr or v==0)return 0;
if(l==ll and r==rr){
return tree[v].val;
}else{
int tt=(l+r)/2;
return getsum(tree[v].l,l,tt,ll,min(tt,rr)) + getsum(tree[v].r,tt+1,r,max(tt+1,ll),rr);
}
}
};
struct ST2D{
struct node{
ST t;
};
node tree[4*MAXN];
void init(){
for(int i=1;i<4*MAXN;i++){
tree[i].t.init();
}
}
void update(int v,int l,int r,int x,int y){
if(l==r){
tree[v].t.update(1,1,maxs,y);
}else{
int tt=(l+r)/2;
if(x<=tt)update(2*v,l,tt,x,y);
else update(2*v+1,tt+1,r,x,y);
tree[v].t.update(1,1,maxs,y);
}
}
int getsum(int v,int l,int r,int lx,int rx,int ly,int ry){
if(lx>rx or v==0)return 0;
if(l==lx and r==rx){
return tree[v].t.getsum(1,1,maxs,ly,ry);
}else{
int tt=(l+r)/2;
return getsum(2*v,l,tt,lx,min(tt,rx),ly,ry) + getsum(2*v+1,tt+1,r,max(tt+1,lx),rx,ly,ry);
}
}
}rivers,vertices,edgesh,edgesv;
int n,m,x,y,minx,miny,maxx,maxy;
map< pair<int,int> , int > ver,eh,ev,riv;
void add(int x,int y){
if(riv[{x,y}]==0){
rivers.update(1,1,maxs,x,y);
riv[{x,y}]=1;
}
for(int i=0;i<=1;i++){
for(int f=0;f<=1;f++){
if(ver[{x+i,y+f}]==1)continue;
vertices.update(1,1,maxs,x+i,y+f);
ver[{x+i,y+f}]=1;
}
}
for(int i=0;i<=0;i++){
for(int f=0;f<=1;f++){
if(ev[{x+i,y+f}]==1)continue;
edgesv.update(1,1,maxs,x+i,y+f);
ev[{x+i,y+f}]=1;
}
}
for(int i=0;i<=1;i++){
for(int f=0;f<=0;f++){
if(eh[{x+i,y+f}]==1)continue;
edgesh.update(1,1,maxs,x+i,y+f);
eh[{x+i,y+f}]=1;
}
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n=R; m=C;
x=sr; y=sc;
rivers.init();
edgesh.init();
edgesv.init();
vertices.init();
add(x,y);
minx=maxx=x;
miny=maxy=y;
for(int i=0;i<M;i++){
if(S[i]=='N')x--;
if(S[i]=='S')x++;
if(S[i]=='E')y++;
if(S[i]=='W')y--;
add(x,y);
minx=min(minx,x);
miny=min(miny,y);
maxx=max(maxx,x);
maxy=max(maxy,y);
}
}
int colour(int ar,int ac,int br,int bc){
int R=rivers.getsum(1,1,maxs,ar,br,ac,bc);
int V=vertices.getsum(1,1,maxs,ar,br+1,ac,bc+1);
int E=edgesv.getsum(1,1,maxs,ar,br,ac,bc+1) + edgesh.getsum(1,1,maxs,ar,br+1,ac,bc);
int horr=2*(bc-ac+1) - edgesh.getsum(1,1,maxs,ar,ar,ac,bc) - edgesh.getsum(1,1,maxs,br+1,br+1,ac,bc) ;
int verr=2*(br-ar+1) - edgesv.getsum(1,1,maxs,ar,br,ac,ac) - edgesv.getsum(1,1,maxs,ar,br,bc+1,bc+1) ;
int Vhor=2*(bc-ac+2) - vertices.getsum(1,1,maxs,ar,ar,ac,bc+1) - vertices.getsum(1,1,maxs,br+1,br+1,ac,bc+1) ;
int Vver=2*(br-ar+2) - vertices.getsum(1,1,maxs,ar,br+1,ac,ac) - vertices.getsum(1,1,maxs,ar,br+1,bc+1,bc+1) ;
E+=horr+verr;
V+=Vhor+Vver;
if(ver[{ar,ac}]==0)V--;
if(ver[{ar,bc+1}]==0)V--;
if(ver[{br+1,ac}]==0)V--;
if(ver[{br+1,bc+1}]==0)V--;
if(minx>ar and maxx<br and miny>ac and maxy<bc){
cout<<1/0;
}
return E-V-R+1;
}
/*int main(){
init(6, 4,3, 3, 9,"NWESSWEWS");
cout<<"bro";
cout<<colour(2,3, 2, 3)<<"\n";
cout<<colour(3,2,4,4)<<"\n";
cout<<colour(5,3,6,4)<<"\n";
cout<<colour(1,2,5,3)<<"\n";
cout<<colour(1,1,6,4)<<":\n";
return 0;
}*/
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:185:16: warning: division by zero [-Wdiv-by-zero]
185 | cout<<1/0;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
200984 KB |
Output is correct |
| 2 |
Correct |
267 ms |
201948 KB |
Output is correct |
| 3 |
Runtime error |
350 ms |
407848 KB |
Execution killed with signal 4 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
200788 KB |
Output is correct |
| 2 |
Correct |
219 ms |
200784 KB |
Output is correct |
| 3 |
Correct |
1967 ms |
352436 KB |
Output is correct |
| 4 |
Execution timed out |
3080 ms |
442248 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
200784 KB |
Output is correct |
| 2 |
Correct |
2334 ms |
422004 KB |
Output is correct |
| 3 |
Correct |
2336 ms |
827200 KB |
Output is correct |
| 4 |
Correct |
2373 ms |
615992 KB |
Output is correct |
| 5 |
Correct |
1820 ms |
570216 KB |
Output is correct |
| 6 |
Correct |
589 ms |
220496 KB |
Output is correct |
| 7 |
Runtime error |
1069 ms |
479312 KB |
Execution killed with signal 4 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
200984 KB |
Output is correct |
| 2 |
Correct |
267 ms |
201948 KB |
Output is correct |
| 3 |
Runtime error |
350 ms |
407848 KB |
Execution killed with signal 4 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
200984 KB |
Output is correct |
| 2 |
Correct |
267 ms |
201948 KB |
Output is correct |
| 3 |
Runtime error |
350 ms |
407848 KB |
Execution killed with signal 4 |
| 4 |
Halted |
0 ms |
0 KB |
- |
