Submission #52343

#	Time	Username	Problem	Language	Result	Execution time	Memory
52343		imeimi2000	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1132 ms	464800 KiB

rainbow

#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 << 2].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;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26