#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
const int MX = (1<<23);
const int N = (1<<18);
int R, C, sr, sc, m;
set<ii> blue;
set<ii> points;
set<ii> edges;
int minR, maxR, minC, maxC;
int root=0;
struct QuadTree {
vi seg[N*2];
int nxt2=1;
void build() {
RE(i,N*2) sort(all(seg[i]));
}
void add(int x, int y, int l=0, int r=N-1, int p=1) {
if(x < l || x > r) return;
seg[p].push_back(y);
if(l == r) return;
int m=(l+r)/2;
add(x, y, l , m, p*2 );
add(x, y, m+1, r, p*2+1);
}
int get(int i, int j, int x, int y, int l=0, int r=N-1, int p=1) {
if(j < l || i > r) return 0;
if(i <= l && j >= r) {
auto lb = lower_bound(all(seg[p]), x);
auto ub = upper_bound(all(seg[p]), y);
return ub - lb;
}
int m = (l+r)/2;
int a = get(i, j, x, y, l , m, p*2 );
int b = get(i, j, x, y, m+1, r, p*2+1);
return a+b;
}
} blueCells, bluePoints, blueLandEdgesH, blueLandEdgesV;
void init(int _R, int _C, int _sr, int _sc, int M, char *S) {
R=_R; C=_C; sr=_sr; sc=_sc;
minR=maxR=sr;
minC=maxC=sc;
RE(i,M) {
blue.insert({sc,sr});
if(S[i] == 'N') sr--;
if(S[i] == 'S') sr++;
if(S[i] == 'E') sc++;
if(S[i] == 'W') sc--;
}
blue.insert({sc,sr});
FOR(p,blue) {
minR = min(minR, p.se);
minC = min(minC, p.fi);
maxR = max(maxR, p.se);
maxC = max(maxC, p.fi);
blueCells.add(p.fi,p.se);
points.insert({p.fi ,p.se });
points.insert({p.fi ,p.se+1});
points.insert({p.fi+1,p.se });
points.insert({p.fi+1,p.se+1});
if(!blue.count({p.fi-1,p.se })) blueLandEdgesV.add(p.fi , p.se );
blueLandEdgesV.add(p.fi+1, p.se );
if(!blue.count({p.fi ,p.se-1})) blueLandEdgesH.add(p.fi , p.se );
blueLandEdgesH.add(p.fi , p.se+1);
}
FOR(p,points)
bluePoints.add(p.fi,p.se);
blueCells.build();
bluePoints.build();
blueLandEdgesH.build();
blueLandEdgesV.build();
}
int colour(int ar, int ac, int br, int bc) {
int blueCellsCnt = blueCells .get(ac ,bc,ar ,br);
int bluePointsCnt = bluePoints.get(ac+1,bc,ar+1,br);
int blueLandEdges = blueLandEdgesH.get(ac,bc,ar+1,br) + blueLandEdgesV.get(ac+1,bc,ar,br);
int W = bc - ac + 1;
int H = br - ar + 1;
int V = W*H - blueCellsCnt;
int F = (W-1)*(H-1) - bluePointsCnt + 1;
int E = (W-1)*H + (H-1)*W - blueLandEdges;
if(ar < minR && maxR < br && ac < minC && maxC < bc)
F++;
return V - E + F - 1;
}
#include "grader.cpp"
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:96:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
96 | if(!blue.count({p.fi-1,p.se })) blueLandEdgesV.add(p.fi , p.se );
| ^~
rainbow.cpp:97:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
97 | blueLandEdgesV.add(p.fi+1, p.se );
| ^~~~~~~~~~~~~~
rainbow.cpp:98:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
98 | if(!blue.count({p.fi ,p.se-1})) blueLandEdgesH.add(p.fi , p.se );
| ^~
rainbow.cpp:99:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
99 | blueLandEdgesH.add(p.fi , p.se+1);
| ^~~~~~~~~~~~~~
In file included from rainbow.cpp:127:
grader.cpp: At global scope:
grader.cpp:8:12: error: redefinition of 'int R'
8 | static int R, C, M, Q;
| ^
rainbow.cpp:34:5: note: 'int R' previously declared here
34 | int R, C, sr, sc, m;
| ^
In file included from rainbow.cpp:127:
grader.cpp:8:15: error: redefinition of 'int C'
8 | static int R, C, M, Q;
| ^
rainbow.cpp:34:8: note: 'int C' previously declared here
34 | int R, C, sr, sc, m;
| ^
In file included from rainbow.cpp:127:
grader.cpp:9:12: error: redefinition of 'int sr'
9 | static int sr, sc;
| ^~
rainbow.cpp:34:11: note: 'int sr' previously declared here
34 | int R, C, sr, sc, m;
| ^~
In file included from rainbow.cpp:127:
grader.cpp:9:16: error: redefinition of 'int sc'
9 | static int sr, sc;
| ^~
rainbow.cpp:34:15: note: 'int sc' previously declared here
34 | int R, C, sr, sc, m;
| ^~
