#include "rainbow.h"
#include <vector>
#include <set>
using namespace std;
/*
V - E + F - C = 1
V = land cells
E = pairs of adjacent land cells
F = 2x2 grids of land cells
C = what we want
Use merge sort trees
* Blue vertices
* Blue horizontal edges (at top endpoint)
* Blue vertical edges (at left endpoint)
* 2x2 grids of white cells (at TL corner)
Also, check if a set of cells surrounding entire snake is captured in the query
1 2 3 4
1 X X X
2 X X X
3 X X X
4 X X X
5 X X
6
*/
struct segtree
{
int l;
int r;
vector<int> v;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void insert(int I, int V)
{
if(r < I || I < l) return;
v.push_back(V);
if(left != NULL)
{
left->insert(I, V);
right->insert(I, V);
}
}
void segtree_sort()
{
sort(v.begin(), v.end());
if(left != NULL)
{
left->segtree_sort();
right->segtree_sort();
}
}
long long query(int L, int R, int V1, int V2) //count the numbers with value in [V1, V2] in range [L, R].
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R)
{
int e1 = -1, e2 = -1;
//smallest index >= v1, largest index <= v2
for(int bit = 19; bit >= 0; bit--)
{
if(e1 + (1 << bit) >= v.size()) continue;
if(v[e1 + (1 << bit)] < V1)
e1 += (1 << bit);
}
e1++;
for(int bit = 19; bit >= 0; bit--)
{
if(e2 + (1 << bit) >= v.size()) continue;
if(v[e2 + (1 << bit)] <= V2)
e2 += (1 << bit);
}
if(e1 == v.size() || e1 == -1 || e2 == -1 || e1 > e2)
return 0;
else
return e2-e1+1;
}
else
{
return left->query(L, R, V1, V2) + right->query(L, R, V1, V2);
}
}
};
segtree cells(0, 200001);
segtree horiz(0, 200001);
segtree vert(0, 200001);
segtree faces(0, 200001);
struct pos
{
int r;
int c;
};
bool operator < (pos A, pos B)
{
if(A.r == B.r) return A.c < B.c;
return A.r < B.r;
};
set<pos> water;
int tp = 1e9, lf = 1e9, dn = -1, rg = 0;
void init(int R, int C, int sr, int sc, int M, char *S)
{
water.insert(pos{sr, sc});
int curr_r = sr;
int curr_c = sc;
for(int i = 0; i < M; i++)
{
// cerr << S[i] << '\n';
if(S[i] == 'N') curr_r--;
else if(S[i] == 'S') curr_r++;
else if(S[i] == 'W') curr_c--;
else if(S[i] == 'E') curr_c++;
// cerr << curr_r << ' ' << curr_c << '\n';
water.insert(pos{curr_r, curr_c});
// cerr << "water: ";
// for(pos w:water) cerr << w.r << ' ' << w.c << " | ";
// cerr << '\n';
}
for(pos w: water)
{
cells.insert(w.r, w.c);
horiz.insert(w.r, w.c);
if(water.find(pos{w.r, w.c-1}) == water.end())
horiz.insert(w.r, w.c-1);
vert.insert(w.r, w.c);
if(water.find(pos{w.r-1, w.c}) == water.end())
vert.insert(w.r-1, w.c);
/*
Preference order: 1 2
3 4
*/
//Face DR
faces.insert(w.r, w.c);
// cerr << "insert " << w.r << ' ' << w.c << '\n';
//Face DL
if(water.find(pos{w.r, w.c-1}) == water.end())
{
faces.insert(w.r, w.c-1);
// cerr << "insert " << w.r << ' ' << w.c-1 << '\n';
}
//Face TR
if(water.find(pos{w.r-1, w.c}) == water.end())
if(water.find(pos{w.r-1, w.c+1}) == water.end())
{
faces.insert(w.r-1, w.c);
// cerr << "insert " << w.r-1 << ' ' << w.c << '\n';
}
//Face TL
if(water.find(pos{w.r-1, w.c}) == water.end())
if(water.find(pos{w.r, w.c-1}) == water.end())
if(water.find(pos{w.r-1, w.c-1}) == water.end())
{
faces.insert(w.r-1, w.c-1);
// cerr << "insert " << w.r-1 << ' ' << w.c-1 << '\n';
}
tp = min(tp, w.r);
dn = max(dn, w.r);
lf = min(lf, w.c);
rg = max(rg, w.c);
}
cells.segtree_sort();
horiz.segtree_sort();
vert.segtree_sort();
faces.segtree_sort();
// cerr << tp << ' ' << dn << ' ' << lf << ' ' << rg << '\n';
}
int colour(int ar, int ac, int br, int bc)
{
long long h = br-ar+1;
long long w = bc-ac+1;
/*
V - E + F - C = 1
C = V-E+F-1
*/
// cerr << "check\n";
long long V = h*w - cells.query(ar, br, ac, bc);
long long E = h*(w-1) + (h-1)*w - vert.query(ar, br-1, ac, bc) - horiz.query(ar, br, ac, bc-1);
long long F = (h-1)*(w-1) - faces.query(ar, br-1, ac, bc-1) + 1;
// cerr << (tp<ar) << (br<dn) << (lf<ac) << (bc<rg) << '\n';
if(ar < tp && dn < br && ac < lf && rg < bc)
F++;
long long C = V - E + F - 1;
// cerr << V << ' ' << E << ' ' << F << ' ' << C << '\n';
return int(C);
}
Compilation message
rainbow.cpp: In member function 'void segtree::segtree_sort()':
rainbow.cpp:70:9: error: 'sort' was not declared in this scope; did you mean 'short'?
70 | sort(v.begin(), v.end());
| ^~~~
| short
rainbow.cpp: In member function 'long long int segtree::query(int, int, int, int)':
rainbow.cpp:89:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if(e1 + (1 << bit) >= v.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
rainbow.cpp:97:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | if(e2 + (1 << bit) >= v.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~
rainbow.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(e1 == v.size() || e1 == -1 || e2 == -1 || e1 > e2)
| ~~~^~~~~~~~~~~
