| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 598716 | GusterGoose27 | Land of the Rainbow Gold (APIO17_rainbow) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef vector<pair<int, vector<int>>> plist;
typedef pair<int, int> pii;
const int MAXN = 2e5+5;
set<int> serpx[MAXN]; // points
set<int> serpy_c[MAXN]; // corners
set<int> serp_c[MAXN]; // corners, (i, j) refers to bottom left of square i, j
vector<pii> rangesx[MAXN];
vector<pii> rangesy[MAXN];
bool valid(int x, int y, set<int> s[] = serp_c) {
if (x < 0) return 0;
return (s[x].find(y) != s[x].end());
}
bool adjy(int x, int y) {
return valid(x, y, serpx) || valid(x-1, y, serpx);
}
bool adjx(int x, int y) {
return valid(x, y, serpx) || valid(x, y-1, serpx);
}
bool xempty(int y, int x1, int x2) {
return (serpy_c[y].lower_bound(x1) == serpy_c[y].upper_bound(x2));
}
bool yempty(int x, int y1, int y2) {
return (serp_c[x].lower_bound(y1) == serp_c[x].upper_bound(y2));
}
int getxcc(int y, int x1, int x2) {
int mn = -1;
int mx = rangesy[y].size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (rangesy[y][cur].second < x1) mn = cur;
else mx = cur;
}
int l = mn;
mn = -1;
mx = rangesy[y].size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (rangesy[y][cur].first > x2) mx = cur;
else mn = cur;
}
return mx-l-1;
}
int getycc(int x, int y1, int y2) {
int mn = -1;
int mx = rangesx[x].size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (rangesx[x][cur].second < y1) mn = cur;
else mx = cur;
}
int l = mn;
mn = -1;
mx = rangesx[x].size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (rangesx[x][cur].first > y2) mx = cur;
else mn = cur;
}
return mx-l-1;
}
class intree {
public:
int ymin, ymax;
int xmin, xmax;
int point_count = 0;
int edge_net = 0;
int u_cut = 0;
int r_cut = 0;
int sq_count = 0;
intree *l = nullptr;
intree *r = nullptr;
intree(plist &vals, int y1, int y2, int lp, int rp) {
ymin = y1;
ymax = y2;
xmin = vals[lp].first;
xmax = vals[rp].first;
if (lp == rp) make_spec(vals[lp].second);
else {
int m = (lp+rp)/2;
l = new intree(vals, y1, y2, lp, m);
r = new intree(vals, y1, y2, m+1, rp);
merge(vals, m);
}
}
void make_spec(vector<int> &vals) {
point_count = vals.size();
for (int v: vals) {
if (adjx(xmin, v)) r_cut++;
if (v < ymax) {
if (adjy(xmin, v)) edge_net++;
//if (valid(xmin, v, serpx)) r_cut--;
}
}
if (vals.back() == ymax) {
if (adjy(xmin, ymax)) u_cut++;
}
for (auto it = serpx[xmin].lower_bound(ymin); it != serpx[xmin].end() && (*it) <= ymax; it++) sq_count++;
}
void merge(plist &vals, int m) {
point_count = l->point_count+r->point_count;
edge_net = l->edge_net+r->edge_net+l->r_cut;
u_cut = l->u_cut+r->u_cut;
r_cut = r->r_cut;
sq_count = l->sq_count+r->sq_count;
// if (vals[m].first == vals[m+1].first && vals[m].second.back() == ymax && vals[m+1].second.back() == ymax) {
// u_cut--;
// }
}
int query(int x1, int x2, int uc, int dc) {
if (xmin > x2 || xmax < x1) return 0;
if (xmin >= x1 && xmax <= x2) {
int lc = (xmin > x1);
int rc = (xmax < x2);
int ans = edge_net-point_count;
if (rc) ans += r_cut;
if (uc) ans += u_cut;
return ans;
}
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;
}
int query2(int x1, int x2) {
if (xmin > x2 || xmax < x1) return 0;
if (xmin >= x1 && xmax <= x2) {
return sq_count;
}
return l->query2(x1, x2)+r->query2(x1, x2);
}
};
class stree {
public:
int ymin, ymax;
plist vals;
intree *curtree = nullptr;
stree *l = nullptr;
stree *r = nullptr;
stree(int y1, int y2) {
ymin = y1;
ymax = y2;
if (ymin == ymax) make_vals_spec();
else {
int m = (ymin+ymax)/2;
l = new stree(y1, m);
r = new stree(m+1, y2);
merge_vals();
}
if (vals.empty()) return;
curtree = new intree(vals, y1, y2, 0, vals.size()-1);
}
void make_vals_spec() {
for (int x: serpy_c[ymin]) vals.push_back(pair<int, vector<int>>(x, {ymin}));
}
vector<int> merge_vec(vector<int> &a, vector<int> &b) {
int g = 0;
int h = 0;
vector<int> v;
while (g < a.size() || h < b.size()) {
if (g == a.size()) {
v.push_back(b[h++]);
continue;
}
if (h == b.size()) {
v.push_back(a[g++]);
continue;
}
if (a[g] < b[h]) {
v.push_back(a[g++]);
}
else v.push_back(b[h++]);
}
return v;
}
void merge_vals() {
int a = 0;
int b = 0;
while (a < l->vals.size() || b < r->vals.size()) {
if (a == l->vals.size()) {
vals.push_back(r->vals[b++]);
continue;
}
if (b == r->vals.size()) {
vals.push_back(l->vals[a++]);
continue;
}
if (l->vals[a].first == r->vals[b].first) {
vals.push_back(pair<int, vector<int>>(l->vals[a].first, merge_vec(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++]);
}
else vals.push_back(r->vals[b++]);
}
}
int query(int x1, int x2, int y1, int y2) {
if (ymin > y2 || ymax < y1 || curtree == nullptr) return 0;
if (ymin >= y1 && ymax <= y2) {
return curtree->query(x1, x2, ymax < y2, ymin > y1);
}
int lq = l->query(x1, x2, y1, y2);
int rq = r->query(x1, x2, y1, y2);
// if (lq == -1) return rq;
// if (rq == -1) return lq;
return lq+rq;
}
int query2(int x1, int x2, int y1, int y2) {
if (ymin > y2 || ymax < y1 || curtree == nullptr) return 0;
if (ymin >= y1 && ymax <= y2) return curtree->query2(x1, x2);
return l->query2(x1, x2, y1, y2)+r->query2(x1, x2, y1, y2);
}
};
stree *tree;
void color(int r, int c) {
serpx[r].insert(c);
serpy_c[c].insert(r);
serpy_c[c].insert(r+1);
serpy_c[c+1].insert(r);
serpy_c[c+1].insert(r+1);
serp_c[r].insert(c);
serp_c[r].insert(c+1);
serp_c[r+1].insert(c);
serp_c[r+1].insert(c+1);
}
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] == 'S') sr++;
if (s[i] == 'W') sc--;
if (s[i] == 'E') sc++;
color(sr, sc);
}
tree = new stree(0, MAXN-1);
pii prev;
for (int x = 0; x < MAXN; x++) {
prev = pii(-1, -1);
for (int y: serp_c[x]) {
if (prev.second == -1) prev = pii(y, y);
else prev.second++;
if (!adjy(x, y)) {
rangesx[x].push_back(prev);
prev = pii(-1, -1);
}
}
}
for (int y = 0; y < MAXN; y++) {
prev = pii(-1, -1);
for (int x: serpy_c[y]) {
if (prev.second == -1) prev = pii(x, x);
else prev.second++;
if (!adjx(x, y)) {
rangesy[y].push_back(prev);
prev = pii(-1, -1);
}
}
}
}
int colour(int x1, int y1, int x2, int y2) {
x1--;
y1--;
int sqs = tree->query2(x1, x2-1, y1, y2-1);
if (sqs == 0) return 1;
int ans = tree->query(x1, x2, y1, y2)-sqs;
//if (xempty(y1, x1, x2) && xempty(y2, x1, x2) && yempty(x1, y1, y2) && yempty(x2, y1, y2)) return ans+2;
int cc = getxcc(y1, x1, x2)+getxcc(y2, x1, x2)+getycc(x1, y1, y2)+getycc(x2, y1, y2);
cc -= valid(x1, y1);
cc -= valid(x1, y2);
cc -= valid(x2, y1);
cc -= valid(x2, y2);
return ans+cc+1;
}
int main() {
init(6, 4, 3, 3, 9, "NWESSWEWS");
//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, 5, 3) << "\n";
return 0;
}