#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 2e5+1;
int n, m;
set<int> serp[MAXN];
vector<int> serpy[MAXN];
bool valid(int x, int y) {
return (serp[x].find(y) != serp[x].end());
}
vector<int> vec_merge(vector<int> &a, vector<int> &b) {
vector<int> v;
int l = 0;
int r = 0;
while (l < a.size() || r < b.size()) {
if (l == a.size()) {
v.push_back(b[r]);
r++;
continue;
}
if (r == b.size()) {
v.push_back(a[l]);
l++;
continue;
}
if (a[l] < b[r]) {
v.push_back(a[l]);
l++;
continue;
}
v.push_back(b[r]);
r++;
}
return v;
}
bool right_seam(int x, int y) {
return valid(x, y) && valid(x, y+1) && valid(x+1, y) && valid(x+1, y+1);
}
bool dubx(int x, int y) {
return valid(x, y) && valid(x+1, y);
}
bool duby(int x, int y) {
return valid(x, y) && valid(x, y+1);
}
class intree {
public:
int lval, rval;
int ymin, ymax;
int n;
intree *l = nullptr;
intree *r = nullptr;
int vert_count = 0;
int u_cut = 0;
int r_cut = 0;
int u_sq = 0;
int r_sq = 0;
int num_edges = 0;
int num_sqs = 0;
int ladj = 0; // edges minus adj nodes
int radj = 0;
int uadj = 0;
int dadj = 0;
intree(vector<pair<int, vector<int>>> &vals, int lpos, int rpos, int y1, int y2) {
ymin = y1;
ymax = y2;
lval = vals[lpos].first;
rval = vals[rpos].first;
n = rpos-lpos+1;
if (lpos == rpos) special_create(vals[lpos]);
else {
int m = (lpos+rpos)/2;
l = new intree(vals, lpos, m, y1, y2);
r = new intree(vals, m+1, rpos, y1, y2);
merge(vals, m);
}
}
void special_create(pair<int, vector<int>> &v) {
int x = v.first;
for (int y: v.second) {
if (valid(x+1, y)) r_cut++;
}
if (v.second.back() == ymax) {
if (valid(x, ymax+1)) u_cut++;
uadj++;
}
if (v.second[0] == ymin) dadj++;
ladj = radj = v.second.size();
for (int i = 0; i < v.second.size()-1; i++) {
if (v.second[i] == v.second[i+1]-1) {
ladj--;
radj--;
num_edges++;
if (duby(x+1, v.second[i])) r_sq++;
}
}
vert_count = v.second.size();
}
void merge(vector<pair<int, vector<int>>> &vals, int m) {
vert_count = l->vert_count+r->vert_count; //
num_edges = l->num_edges+r->num_edges+l->r_cut; //
num_sqs = l->num_sqs+r->num_sqs+l->r_sq; //
ladj = l->ladj; //
radj = r->radj; //
uadj = l->uadj+r->uadj; //
dadj = l->dadj+r->dadj; //
u_cut = l->u_cut+r->u_cut; //
r_cut = r->r_cut; //
r_sq = r->r_sq; //
u_sq = l->u_sq+r->u_sq; //
int xdiv = vals[m].first;
if (vals[m].first+1 == vals[m+1].first) {
if (vals[m].second.back() == ymax && vals[m+1].second.back() == ymax) {
uadj--;
if (dubx(xdiv, ymax+1)) u_sq++;
}
if (vals[m].second[0] == ymin && vals[m+1].second[0] == ymin) dadj--;
}
}
int query(int x1, int x2, int uc, int dc) { // srmask bits go right up left down. Return e-v-sq
if (lval > x2 || rval < x1) return 0;
if (lval >= x1 && rval <= x2) {
int srmask = 2*uc+8*dc;
if (rval < x2) srmask++;
if (lval > x1) srmask += 4;
int s = num_edges-vert_count-num_sqs;
if (srmask & 1) {
s += r_cut-r_sq;
}
if (srmask & 2) {
s += u_cut-u_sq;
}
if ((srmask & 1) == 0) {
s += radj;
}
if ((srmask & 2) == 0) {
s += uadj;
}
if ((srmask & 4) == 0) {
s += ladj;
}
if ((srmask & 8) == 0) {
s += dadj;
}
if (srmask & 3) s -= right_seam(rval, ymax);
if ((srmask & 2) && !(srmask & 1)) s -= duby(rval, ymax);
if (!(srmask & 2) && (srmask & 1)) s -= dubx(rval, ymax);
if ((srmask & 2) && !(srmask & 4)) s -= duby(lval, ymax);
if ((srmask & 1) && !(srmask & 8)) s -= dubx(rval, ymin);
return s;
}
return l->query(x1, x2, uc, dc)+r->query(x1, x2, uc, dc);
}
};
class stree {
public:
intree *cur_tree;
int y1, y2;
stree *l = nullptr;
stree *r = nullptr;
vector<pair<int, vector<int>>> vals;
stree(int dval, int uval) {
y1 = dval;
y2 = uval;
if (y1 == y2) make_vals();
else {
int m = (y1+y2)/2;
l = new stree(dval, m);
r = new stree(m+1, uval);
merge_vals();
}
if (vals.size() > 0) cur_tree = new intree(vals, 0, vals.size()-1, y1, y2);
}
void make_vals() {
for (int x: serpy[y1]) {
vals.push_back(pair<int, vector<int>>(x, {y1}));
}
}
void merge_vals() {
int m1 = l->vals.size();
int m2 = r->vals.size();
int a = 0;
int b = 0;
while (a < m1 || b < m2) {
if (a == m1) {
vals.push_back(r->vals[b]);
b++;
continue;
}
if (b == m2) {
vals.push_back(l->vals[a]);
a++;
continue;
}
if (l->vals[a].first == r->vals[b].first) {
vals.push_back(pair<int, vector<int>>(l->vals[a].first, vec_merge(l->vals[a].second, r->vals[b].second)));
a++;
b++;
continue;
}
if (l->vals[a].first < r->vals[b].first) {
vals.push_back(l->vals[a]);
a++;
continue;
}
vals.push_back(r->vals[b]);
b++;
}
}
int query(int dy, int uy, int x1, int x2) {
if (cur_tree == nullptr) return 0;
if (y1 > uy || y2 < dy) return 0;
if (y1 >= dy && y2 <= uy) {
int uadj = 0;
int dadj = 0;
if (y1 > dy) dadj = 1;
if (y2 < uy) uadj = 1;
return cur_tree->query(x1, x2, uadj, dadj);
}
return l->query(dy, uy, x1, x2)+r->query(dy, uy, x1, x2);
}
};
stree *tree;
void color(int r, int c) {
serp[r].insert(c);
}
void init(int t1, int t2, int sr, int sc, int m, string s) {
sr--; sc--;
color(sr, sc);
for (int i = 0; i < m; i++) {
if (s[i] == 'N') sr--;
if (s[i] == 'W') sc--;
if (s[i] == 'S') sr++;
if (s[i] == 'E') sc++;
color(sr, sc);
}
for (int x = 0; x < MAXN; x++) {
for (int y: serp[x]) {
serpy[y].push_back(x);
}
}
tree = new stree(0, MAXN-1);
}
int colours(int x1, int y1, int x2, int y2) {
x1--; y1--; x2--; y2--;
int ans = tree->query(y1, y2, x1, x2);
if (valid(x1, y1)) ans--;
if (valid(x1, y2)) ans--;
if (valid(x2, y1)) ans--;
if (valid(x2, y2)) ans--;
return ans+1;
}
int main() {
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";
return 0;
}
Compilation message
rainbow.cpp: In function 'std::vector<int> vec_merge(std::vector<int>&, std::vector<int>&)':
rainbow.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | while (l < a.size() || r < b.size()) {
| ~~^~~~~~~~~~
rainbow.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | while (l < a.size() || r < b.size()) {
| ~~^~~~~~~~~~
rainbow.cpp:21:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if (l == a.size()) {
| ~~^~~~~~~~~~~
rainbow.cpp:26:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if (r == b.size()) {
| ~~^~~~~~~~~~~
rainbow.cpp: In member function 'void intree::special_create(std::pair<int, std::vector<int> >&)':
rainbow.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 0; i < v.second.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccc2VpTJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccTMIXiJ.o:rainbow.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccc2VpTJ.o: in function `main':
grader.cpp:(.text.startup+0xed): undefined reference to `init(int, int, int, int, int, char*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x167): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status
