#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
const int MAXC = 2e5 + 5;
struct Node {
int vertices, horiEdges, vertEdges, river;
friend Node operator + (const Node &a, const Node &b) {
return {a.vertices + b.vertices, a.horiEdges + b.horiEdges, a.vertEdges + b.vertEdges, a.river + b.river};
}
friend Node operator - (const Node &a, const Node &b) {
return {a.vertices - b.vertices, a.horiEdges - b.horiEdges, a.vertEdges - b.vertEdges, a.river - b.river};
}
};
const Node null{0, 0, 0, 0};
Node st[MAX];
int id, pl[MAX], pr[MAX];
int newLeaf(const Node &cur) {
int p = id++;
st[p] = cur;
pl[p] = pr[p] = 0;
return p;
}
int newParent(int a, int b) {
int p = id++;
st[p] = st[a] + st[b];
pl[p] = a;
pr[p] = b;
return p;
}
Node query(int p1, int p2, int l, int r, int i, int j) {
if (i > r || j < l)
return null;
if (i <= l && r <= j)
return st[p2] - st[p1];
int m = (l + r) / 2;
return query(pl[p1], pl[p2], l, m, i, j) + query(pr[p1], pr[p2], m + 1, r, i, j);
}
int update(int p, int l, int r, int i, const Node &cur) {
if (l == r)
return newLeaf(st[p] + cur);
int m = (l + r) / 2;
if (i <= m)
return newParent(update(pl[p], l, m, i, cur), pr[p]);
else
return newParent(pl[p], update(pr[p], m + 1, r, i, cur));
}
int n, m, mnR, mxR, mnC, mxC, pseg[MAXC];
set<int> cells[MAXC];
map<int, Node> build[MAXC];
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
st[0] = null;
pl[0] = pr[0] = 0;
id = 1;
mnR = mxR = sr;
mnC = mxC = sc;
cells[sc].insert(sr);
for (int i=0; i<M; i++) {
if (S[i] == 'N') sr--;
else if (S[i] == 'S') sr++;
else if (S[i] == 'E') sc++;
else sc--;
mnR = min(mnR, sr);
mxR = max(mxR, sr);
mnC = min(mnC, sc);
mxC = max(mxC, sc);
cells[sc].insert(sr);
}
for (int c=1; c<=m; c++)
for (int r : cells[c]) {
// bottom right
build[r+1][c+1].vertices++;
// bottom left
if (!cells[c-1].count(r) && !cells[c-1].count(r + 1))
build[r+1][c].vertices++;
// top right
if (!cells[c].count(r - 1))
build[r][c+1].vertices++;
// top left
if (!cells[c-1].count(r) && !cells[c-1].count(r - 1) && !cells[c].count(r - 1))
build[r][c].vertices++;
// bottom and right
build[r+1][c].horiEdges++;
build[r][c+1].vertEdges++;
// left
if (!cells[c-1].count(r))
build[r][c].vertEdges++;
// top
if (!cells[c].count(r - 1))
build[r][c].horiEdges++;
build[r][c].river++;
}
for (int i=1; i<=n+1; i++) {
pseg[i] = pseg[i-1];
for (const auto &p : build[i])
pseg[i] = update(pseg[i], 0, m, p.first, p.second);
}
}
int colour(int ar, int ac, int br, int bc) {
int vertices = query(pseg[ar], pseg[br], 0, m, ac + 1, bc).vertices;
int edges = query(pseg[ar], pseg[br], 0, m, ac, bc).horiEdges + query(pseg[ar-1], pseg[br], 0, m, ac + 1, bc).vertEdges;
int river = query(pseg[ar-1], pseg[br], 0, m, ac, bc).river;
int comp = mnR > ar && mxR < br && mnC > ac && mxC < bc ? 2 : 1;
return edges + comp - vertices - river;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19028 KB |
Output is correct |
| 2 |
Incorrect |
154 ms |
39628 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
