#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct BIT2D{
set<pair<int, int>> S;
vector<vector<int>> bit;
int R, C;
void init(int _R, int _C){
R = _R;
C = _C;
bit.resize(R+1);
}
void upd(int x, int y){ // updatea la posicion {x, y} con += 1
if(x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) return;
S.insert({x, y});
for(int i = x; i<=R; i+= i&(-i)){
bit[i].emplace_back(y);
}
}
void build(){
for(int i = 1; i<=R; ++i){
sort(bit[i].begin(), bit[i].end());
}
}
int qry(int x, int y){
int res = 0;
for(int i = x; i>0; i -= i&(-i)){
res += upper_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin();
}
return res;
}
ll qry(int lx, int ly, int rx, int ry){
return 1LL * (rx-lx+1) * (ry-ly+1) - qry(rx, ry) + qry(rx, ly-1) + qry(lx-1, ry) - qry(lx-1, ly-1);
}
}V, rowE, colE, F;
int max_X, min_X, max_Y, min_Y;
void add(int cx, int cy){
max_X = max(max_X, cx);
min_X = min(min_X, cx);
max_Y = max(max_Y, cy);
min_Y = min(min_Y, cy);
V.upd(cx, cy);
rowE.upd(cx-1, cy);
rowE.upd(cx, cy);
colE.upd(cx, cy-1);
colE.upd(cx, cy);
F.upd(cx-1, cy-1);
F.upd(cx-1, cy);
F.upd(cx, cy-1);
F.upd(cx, cy);
}
void init(int R, int C, int cx, int cy, int M, char *S){
V.init(R, C);
rowE.init(R, C);
colE.init(R, C);
F.init(R, C);
max_X = min_X = cx;
max_Y = min_Y = cy;
add(cx, cy);
for(int i = 0; i<M; ++i){
if(S[i] == 'N'){
cx--;
}else if(S[i] == 'E'){
cy++;
}else if(S[i] == 'W'){
cy--;
}else{
cx++;
}
add(cx, cy);
}
V.build();
rowE.build();
colE.build();
F.build();
}
int colours(int lx, int ly, int rx, int ry){
return V.qry(lx, ly, rx, ry) - rowE.qry(lx, ly, rx-1, ry) - colE.qry(lx, ly, rx, ry-1) + F.qry(lx, ly, rx-1, ry-1) + (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry);
}
/*
int main(){
#ifdef _DEBUG
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
init(6, 4, 3, 3, 9, "NWESSWEWS");
cout << colours(2, 3, 2, 3) << "\n";
cout << colours(3, 2, 4, 4) << "\n";
cout << colours(5, 3, 6, 4) << "\n";
cout << colours(1, 2, 5, 3) << "\n";
}
*/
Compilation message
/usr/bin/ld: /tmp/ccCsnEd0.o: in function `main':
grader.cpp:(.text.startup+0x167): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status
