#include "rainbow.h"
#include <algorithm>
using namespace std;
int r, c, m;
struct node {
node *l, *r;
int x;
node() : l(0), r(0), x(0) {}
} ns[100001][20], xs[200002][20], ys[200002][20], vs[200004][20];
node n0;
node * _rt[100002], * _xt[200003], * _yt[200003], * _vt[200005];
node * rt[200001], * xt[200002], * yt[200002], * vt[200002];
void update(node * p, node * q, int s, int e, int x) {
if (s == e) {
q->x = p->x + 1;
return;
}
int m = (s + e) / 2;
if (x <= m) {
q->l = q + 1;
q->r = p->r;
update(p->l, q->l, s, m, x);
}
else {
q->l = p->l;
q->r = q + 1;
update(p->r, q->r, m + 1, e, x);
}
q->x = q->l->x + q->r->x;
}
int query(node * p, node * q, int s, int e, int x, int y) {
if (e < x || y < s) return 0;
if (x <= s && e <= y) return q->x - p->x;
int m = (s + e) / 2;
return query(p->l, q->l, s, m, x, y) + query(p->r, q->r, m + 1, e, x, y);
}
struct point {
int x, y;
point move(char c) const {
if (c == 'N') return { x - 1, y };
if (c == 'S') return { x + 1, y };
if (c == 'W') return { x, y - 1 };
return { x, y + 1 };
}
bool operator<(const point &p) const {
if (x == p.x) return y < p.y;
return x < p.x;
}
bool operator==(const point &p) const {
return x == p.x && y == p.y;
}
} ps[100001], px[200002], py[200002], pv[400004];
int mnx, mny, mxx, mxy;
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
m = M;
rt[0] = xt[0] = yt[0] = vt[0] = &n0;
_rt[0] = _xt[0] = _yt[0] = _vt[0] = &n0;
n0.l = n0.r = &n0;
ps[0] = { sr, sc };
mnx = mxx = sr;
mny = mxy = sc;
for (int i = 0; i < m; ++i) {
ps[i + 1] = ps[i].move(S[i]);
mnx = min(mnx, ps[i + 1].x);
mxx = max(mxx, ps[i + 1].x);
mny = min(mny, ps[i + 1].y);
mxy = max(mxy, ps[i + 1].y);
}
sort(ps, ps + (m + 1));
m = unique(ps, ps + (m + 1)) - ps;
for (int i = 0; i < m; ++i) {
px[i << 1] = px[i << 1 | 1] = ps[i];
--px[i << 1].x;
py[i << 1] = py[i << 1 | 1] = ps[i];
--py[i << 1].y;
pv[i << 2] = pv[i << 2 | 1] = pv[i << 2 | 2] = pv[i << 2 | 3] = ps[i];
--pv[i << 2].x;
--pv[i << 1].y;
--pv[i << 2 | 1].x;
--pv[i << 2 | 2].y;
}
sort(px, px + (m << 1));
int nx = unique(px, px + (m << 1)) - px;
sort(py, py + (m << 1));
int ny = unique(py, py + (m << 1)) - py;
sort(pv, pv + (m << 2));
int nv = unique(pv, pv + (m << 2)) - pv;
for (int i = 0, ip = 0, ix = 0, iy = 0, iv = 0; i <= 200000; ++i) {
while (ip < m && ps[ip].x == i) {
update(_rt[ip], _rt[ip + 1] = ns[ip], 0, c, ps[ip].y);
++ip;
}
rt[i] = _rt[ip];
while (ix < nx && px[ix].x == i) {
update(_xt[ix], _xt[ix + 1] = xs[ix], 0, c, px[ix].y);
++ix;
}
xt[i + 1] = _xt[ix];
while (iy < ny && py[iy].x == i) {
update(_yt[iy], _yt[iy + 1] = ys[iy], 0, c, py[iy].y);
++iy;
}
yt[i + 1] = _yt[iy];
while (iv < nv && pv[iv].x == i) {
update(_vt[iv], _vt[iv + 1] = vs[iv], 0, c, pv[iv].y);
++iv;
}
vt[i + 1] = _vt[iv];
}
}
int colour(int ar, int ac, int br, int bc) {
int ret = 1;
if (ar < mnx && mxx < br && ac < mny && mxy < bc) ret = 2;
int ct = br + bc - ar - ac + 2;
ct <<= 1;
int v = ct;
v += query(vt[ar], vt[br], 0, c, ac, bc - 1);
int e = ct;
e += query(xt[ar], xt[br], 0, c, ac, bc);
e += query(yt[ar], yt[br + 1], 0, c, ac, bc - 1);
int pf = query(rt[ar - 1], rt[br], 0, c, ac, bc);
ret -= v;
ret += e;
ret -= pf;
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
335448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
335544 KB |
Output is correct |
| 2 |
Correct |
235 ms |
335752 KB |
Output is correct |
| 3 |
Incorrect |
677 ms |
346176 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
346176 KB |
Output is correct |
| 2 |
Correct |
427 ms |
350496 KB |
Output is correct |
| 3 |
Incorrect |
379 ms |
350512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
335448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
335448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
