#include "rainbow.h"
#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;
const int MXn = 2e5 + 5;
const int dx[] = {1, 0, 1};
const int dy[] = {0, 1, 1};
int n, m;
struct PST {
vector<int> val, idL, idR;
void resiz(int s) {
val.resize(s + 3, 0);
idL.resize(s + 3, -1);
idR.resize(s + 3, -1);
}
int no = 0;
int build(int l = 1, int r = n) {
int cur = ++no;
assert(cur < sz(val));
val[cur] = 0;
if (l == r) return cur;
int mid = (l + r) >> 1;
idL[cur] = build(l, mid);
idR[cur] = build(mid + 1, r);
return cur;
}
int update(int i, int v, int oID, int l = 1, int r = n) {
int cur = ++no;
assert(cur < sz(val));
if (l == r) {
val[cur] = val[oID] + v;
return cur;
}
int mid = (l + r) >> 1;
if (i <= mid) {
idL[cur] = update(i, v, idL[oID], l, mid);
idR[cur] = idR[oID];
} else {
idL[cur] = idL[oID];
idR[cur] = update(i, v, idR[oID], mid + 1, r);
}
val[cur] = val[idL[cur]] + val[idR[cur]];
return cur;
}
int get(int Lf, int Rt, int id, int l = 1, int r = n) {
if (Lf <= l && r <= Rt) {
return val[id];
}
int mid = (l + r) >> 1;
int res = 0;
if (Lf <= mid) res += get(Lf, Rt, idL[id], l, mid);
if (Rt > mid) res += get(Lf, Rt, idR[id], mid + 1, r);
return res;
}
} T[4];
int root[4][MXn];
bool onboard(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
vector<int> river[MXn], v1[MXn], v2[MXn], v3[MXn];
int x1 = MXn, x2 = -MXn, y1 = MXn, y2 = -MXn;
void add(int sr, int sc) {
x1 = min(x1, sr);
x2 = max(x2, sr);
y1 = min(y1, sc);
y2 = max(y2, sc);
assert(onboard(sr, sc));
river[sc].emplace_back(sr);
if (sc > 1) v1[sc - 1].emplace_back(sr);
v1[sc].emplace_back(sr);
if (sr > 1) v2[sc].emplace_back(sr - 1);
v2[sc].emplace_back(sr);
v3[sc].emplace_back(sr);
for (int k = 0; k < 3; k++) {
int xx = dx[k] + sr, yy = dy[k] + sc;
if (onboard(xx, yy)) v3[yy].emplace_back(xx);
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
add(sr, sc);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
if (S[i] == 'E') sc++;
add(sr, sc);
}
vector<int> siz(4, 0);
for (int c = 1; c <= C; c++) {
sort(begin(river[c]), end(river[c]));
river[c].resize(unique(begin(river[c]), end(river[c])) - river[c].begin());
siz[0] += sz(river[c]);
sort(begin(v1[c]), end(v1[c]));
v1[c].resize(unique(begin(v1[c]), end(v1[c])) - v1[c].begin());
siz[1] += sz(v1[c]);
sort(begin(v2[c]), end(v2[c]));
v2[c].resize(unique(begin(v2[c]), end(v2[c])) - v2[c].begin());
siz[2] += sz(v2[c]);
sort(begin(v3[c]), end(v3[c]));
v3[c].resize(unique(begin(v3[c]), end(v3[c])) - v3[c].begin());
siz[3] += sz(v3[c]);
}
for (int t = 0; t < 4; t++) {
T[t].resiz((1 << 19) + siz[t] * 19);
root[t][0] = T[t].build();
}
for (int c = 1; c <= C; c++) {
root[0][c] = root[0][c - 1];
root[1][c] = root[1][c - 1];
root[2][c] = root[2][c - 1];
root[3][c] = root[3][c - 1];
for (int r: river[c]) {
root[0][c] = T[0].update(r, 1, root[0][c]);
}
for (int r: v1[c]) {
root[1][c] = T[1].update(r, 1, root[1][c]);
}
for (int r: v2[c]) {
root[2][c] = T[2].update(r, 1, root[2][c]);
}
for (int r: v3[c]) {
root[3][c] = T[3].update(r, 1, root[3][c]);
}
}
}
int colour(int ar, int ac, int br, int bc) {
long long V = (br - ar + 1) * (bc - ac + 1) - (T[0].get(ar, br, root[0][bc]) - T[0].get(ar, br, root[0][ac - 1]));
long long E = (bc - ac) * (br - ar + 1) - (T[1].get(ar, br, root[1][bc - 1]) - T[1].get(ar, br, root[1][ac - 1])) + (bc - ac + 1) * (br - ar);
long long F = 0;
if (ar < br) {
E -= (T[2].get(ar, br - 1, root[2][bc]) - T[2].get(ar, br - 1, root[2][ac - 1]));
F = (br - ar) * (bc - ac) - (T[3].get(ar + 1, br, root[3][bc]) - T[3].get(ar + 1, br, root[3][ac]));
}
if (ar < x1 && x2 < br && ac < y1 && y2 < bc) F++;
return V - E + F;
}
Compilation message
rainbow.cpp:64:26: error: 'int y1' redeclared as different kind of entity
64 | int x1 = MXn, x2 = -MXn, y1 = MXn, y2 = -MXn;
| ^~
In file included from /usr/include/features.h:461,
from /usr/include/x86_64-linux-gnu/c++/10/bits/os_defines.h:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/c++config.h:518,
from /usr/include/c++/10/cassert:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from rainbow.cpp:2:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:221:1: note: previous declaration 'double y1(double)'
221 | __MATHCALL (y1,, (_Mdouble_));
| ^~~~~~~~~~
rainbow.cpp: In function 'void add(int, int)':
rainbow.cpp:68:17: error: no matching function for call to 'min(double (&)(double) throw (), int&)'
68 | y1 = min(y1, sc);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from rainbow.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
rainbow.cpp:68:17: note: deduced conflicting types for parameter 'const _Tp' ('double(double)' and 'int')
68 | y1 = min(y1, sc);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from rainbow.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
rainbow.cpp:68:17: note: deduced conflicting types for parameter 'const _Tp' ('double(double)' and 'int')
68 | y1 = min(y1, sc);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from rainbow.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
rainbow.cpp:68:17: note: mismatched types 'std::initializer_list<_Tp>' and 'double (*)(double) throw ()' {aka 'double (*)(double)'}
68 | y1 = min(y1, sc);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from rainbow.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
rainbow.cpp:68:17: note: mismatched types 'std::initializer_list<_Tp>' and 'double (*)(double) throw ()' {aka 'double (*)(double)'}
68 | y1 = min(y1, sc);
| ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:140:32: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
140 | if (ar < x1 && x2 < br && ac < y1 && y2 < bc) F++;
| ~~~^~~~
