| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 885423 | pubin06 | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 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 "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;
}