#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 2e5+1;
int n, m;
set<int> serp[MAXN];
set<int> serpy[MAXN];
bool valid(int x, int y) {
return (serp[x].find(y) != serp[x].end());
}
bool xempty(int y, int x1, int x2) {
return serpy[y].lower_bound(x1) == serpy[y].lower_bound(x2);
}
bool yempty(int x, int y1, int y2) {
return serp[x].lower_bound(y1) == serp[x].lower_bound(y2);
}
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 || vert_count == 0) return -1;
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;
}
int lq = l->query(x1, x2, uc, dc);
int rq = r->query(x1, x2, uc, dc);
if (lq == -1) return rq;
if (rq == -1) return lq;
return lq+rq;
}
};
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 -1;
if (y1 > uy || y2 < dy) return -1;
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);
}
int lq = l->query(dy, uy, x1, x2);
int rq = r->query(dy, uy, x1, x2);
if (lq == -1) return rq;
if (rq == -1) return lq;
return lq+rq;
}
};
stree *tree;
void color(int r, int c) {
serp[r].insert(c);
}
void init(int t1, int t2, int sr, int sc, int m, char *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].insert(x);
}
}
tree = new stree(0, MAXN-1);
}
int colour(int x1, int y1, int x2, int y2) {
x1--; y1--; x2--; y2--;
int ans = tree->query(y1, y2, x1, x2);
if (xempty(y1, x1, x2+1) && xempty(y2, x1, x2+1) && yempty(x1, y1, y2+1) && yempty(x2, y1, y2+1)) return ans+2;
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, 1, "N");
// cout << colour(2, 3, 2, 3) << "\n";
// cout << colour(3, 2, 4, 4) << "\n";
// cout << colour(5, 3, 6, 4) << "\n";
// cout << colour(1, 2, 4, 4) << "\n";
// cout << colour(2, 2, 3, 4) << "\n";
// return 0;
// }
Compilation message
rainbow.cpp: In function 'std::vector<int> vec_merge(std::vector<int>&, std::vector<int>&)':
rainbow.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while (l < a.size() || r < b.size()) {
| ~~^~~~~~~~~~
rainbow.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while (l < a.size() || r < b.size()) {
| ~~^~~~~~~~~~
rainbow.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if (l == a.size()) {
| ~~^~~~~~~~~~~
rainbow.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if (r == b.size()) {
| ~~^~~~~~~~~~~
rainbow.cpp: In member function 'void intree::special_create(std::pair<int, std::vector<int> >&)':
rainbow.cpp:105:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < v.second.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
44372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
44044 KB |
Output is correct |
| 2 |
Correct |
30 ms |
44048 KB |
Output is correct |
| 3 |
Runtime error |
148 ms |
151408 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
44108 KB |
Output is correct |
| 2 |
Correct |
134 ms |
95512 KB |
Output is correct |
| 3 |
Correct |
407 ms |
529548 KB |
Output is correct |
| 4 |
Correct |
278 ms |
308984 KB |
Output is correct |
| 5 |
Correct |
246 ms |
299752 KB |
Output is correct |
| 6 |
Correct |
101 ms |
64904 KB |
Output is correct |
| 7 |
Incorrect |
182 ms |
83364 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
44372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
44372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
