#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn=2e5+10;
bool flag[2][mxn];
int dm[4]={-1,0,1,0};
int dn[4]={0,1,0,-1};
char dir[4]={'N','E','S','W'};
struct dt {
int cnt; bool ul,dl,ur,dr;
};
dt t[3][3*mxn];
dt unite(dt l,dt r) {
dt res;
res.cnt=l.cnt+r.cnt;
res.ul=l.ul; res.dl=l.dl;
res.ur=r.ur; res.dr=r.dr;
if(l.cnt and r.cnt) {
if((!l.ur and !r.ul) or (!l.dr and !r.dl)) res.cnt--;
}
return res;
}
void build(int v,int tl,int tr) {
if(tl>tr) return;
if(tl==tr) {
if(flag[0][tl] and flag[1][tl]) {
t[2][v]={0,true,true,true,true};
}
else {
t[2][v]={1,flag[0][tl],flag[1][tl],flag[0][tl],flag[1][tl]};
}
return;
}
int mid=(tl+tr)/2;
build(2*v,tl,mid); build(2*v+1,mid+1,tr);
t[2][v]=unite(t[2][2*v],t[2][2*v+1]);
}
void debugdt(dt x) {
cout<<"#"<<": "<<x.cnt<<endl;
}
dt query(int idx,int v,int tl,int tr,int l,int r) {
if(tl>tr or tl>r or tr<l) return {0,1,1,1,1};
if(tl>=l and tr<=r) return t[idx][v];
int mid=(tl+tr)/2;
dt L=query(idx,2*v,tl,mid,l,r);
dt R=query(idx,2*v+1,mid+1,tr,l,r);
dt res=unite(L,R);
// debug(L.cnt,R.cnt,res.cnt);
return unite(L,R);
}
int r,c;
void build2(int idx,int v,int tl,int tr) {
if(tl>tr) return;
if(tl==tr) {
t[idx][v]={!flag[idx][tl],1,1,1,1};
}
else {
int mid=(tl+tr)/2;
build2(idx,2*v,tl,mid);
build2(idx,2*v+1,mid+1,tr);
t[idx][v]=unite(t[idx][2*v],t[idx][2*v+1]);
}
}
void deebug(int idx,int v,int tl,int tr) {
if(tl>tr) return;
cout<<"# {"<<tl<<" "<<tr<<"}"<<": "<<t[idx][v].cnt<<endl;
if(tl==tr) return;
int mid=(tl+tr)/2;
deebug(idx,2*v,tl,mid);
deebug(idx,2*v+1,mid+1,tr);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
r=R,c=C;
--sr; --sc;
flag[sr][sc]=true;
for(int i=0;i<M;i++) {
for(int j=0;j<4;j++) {
if(S[i]==dir[j]) {
sr+=dm[j]; sc+=dn[j]; break;
}
}
flag[sr][sc]=true;
}
// for(int i=0;i<R;i++) {
// for(int j=0;j<C;j++) {
// cout<<flag[i][j]<<" ";
// }
// cout<<endl;
// }
build(1,0,C-1);
for(int i=0;i<2;i++) {
build2(i,1,0,C-1);
}
// deebug(2,1,0,c-1);
}
int colour(int ar, int ac, int br, int bc) {
dt ans;
--ar; --ac; --br; --bc;
if(ar==br) {
ans=query(ar,1,0,c-1,ac,bc);
}
else {
ans=query(2,1,0,c-1,ac,bc);
}
return ans.cnt;
}
Compilation message
rainbow.cpp: In function 'dt query(int, int, int, int, int, int)':
rainbow.cpp:80:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
80 | dt res=unite(L,R);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
716 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
