#include "rainbow.h"
#include <iostream>
#include <array>
#include <vector>
#include <map>
#define ll long long
using namespace std;
vector <array<ll, 2>> V;
map <array<ll, 2>, ll> mp, vert, edger, edgec;
string T = "NESW";
vector <ll> VR[200001], VC[200001], ER[200001], EC[200001];
ll x, y, r, c, nx, ny, tot, e, v, f, dj[4][2] = {0, 0, 0, 1, 1, 0, 1, 1}, dr[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R, c = C;
mp.clear();
V.clear();
V.push_back({sr, sc});
x = sr, y = sc;
for (int j=0; j<M; ++j) {
auto u = S[j];
for (int i=0; i<4; ++i) {
if (u == T[i]) {
nx = x + dr[i][0], ny = y + dr[i][1];
x = nx, y = ny;
V.push_back({x, y});
break;
}
}
}
for (int i=0; i<V.size(); ++i) {
--V[i][0], --V[i][1];
x = V[i][0], y = V[i][1], tot = 0;
if (!mp.count({x, y})) ++mp[{x, y}];
for (int j=0; j<4; ++j) {
nx = x + dj[j][0], ny = y + dj[j][1];
++vert[{nx, ny}];
}
++edger[{x, y}];
++edger[{x+1, y}];
++edgec[{x, y}];
++edgec[{x, y+1}];
}
for (auto it = edger.begin(); it != edger.end();) {
auto nx = next(it);
auto [x, y] = it->first;
ER[x].push_back(y);
it = nx;
}
for (auto it = edgec.begin(); it != edgec.end();) {
auto nx = next(it);
auto [x, y] = it->first;
EC[y].push_back(x);
it = nx;
}
for (auto it = vert.begin(); it != vert.end();) {
auto nxt = next(it);
auto [x, y] = it->first;
VR[x].push_back(y);
VC[y].push_back(x);
it = nxt;
}
for (int i=0; i<=R; ++i) {
sort(VR[i].begin(), VR[i].end());
sort(ER[i].begin(), ER[i].end());
}
for (int i=0; i<=C; ++i) {
sort(VC[i].begin(), VC[i].end());
sort(EC[i].begin(), EC[i].end());
}
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
e = edger.size() + edgec.size() + (br-ar+bc-ac) * 2;
auto it = lower_bound(ER[ar].begin(), ER[ar].end(), ac);
auto it2 = lower_bound(ER[ar].begin(), ER[ar].end(), bc);
e -= (it2-ER[ar].begin())-(it-ER[ar].begin());
it = lower_bound(ER[br].begin(), ER[br].end(), ac);
it2 = lower_bound(ER[br].begin(), ER[br].end(), bc);
e -= (it2-ER[br].begin())-(it-ER[br].begin());
it = lower_bound(EC[ac].begin(), EC[ac].end(), ar);
it2 = lower_bound(EC[ac].begin(), EC[ac].end(), br);
e -= (it2-EC[ac].begin())-(it-EC[ac].begin());
it = lower_bound(EC[bc].begin(), EC[bc].end(), ar);
it2 = lower_bound(EC[bc].begin(), EC[bc].end(), br);
e -= (it2-EC[bc].begin())-(it-EC[bc].begin());
v = vert.size() + (br-ar+bc-ac) * 2;
it = lower_bound(VR[ar].begin(), VR[ar].end(), ac);
it2 = lower_bound(VR[ar].begin(), VR[ar].end(), bc+1);
v -= (it2-VR[ar].begin())-(it-VR[ar].begin());
it = lower_bound(VR[br].begin(), VR[br].end(), ac);
it2 = lower_bound(VR[br].begin(), VR[br].end(), bc+1);
v -= (it2-ER[br].begin())-(it-ER[br].begin());
it = lower_bound(VC[ac].begin(), VC[ac].end(), ar+1);
it2 = lower_bound(VC[ac].begin(), VC[ac].end(), br);
v -= (it2-VC[ac].begin())-(it-VC[ac].begin());
it = lower_bound(VC[bc].begin(), VC[bc].end(), ar+1);
it2 = lower_bound(VC[bc].begin(), VC[bc].end(), br);
v -= (it2-VC[bc].begin())-(it-VC[bc].begin());
f = e-v+1;
return f-mp.size();
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i=0; i<V.size(); ++i) {
| ~^~~~~~~~~
rainbow.cpp:66:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
66 | sort(VR[i].begin(), VR[i].end());
| ^~~~
| qsort
rainbow.cpp:70:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
70 | sort(VC[i].begin(), VC[i].end());
| ^~~~
| qsort
