Submission #49582

#	Time	Username	Problem	Language	Result	Execution time	Memory
49582		model_code	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1630 ms	233976 KiB

rainbow

#include <bits/stdc++.h>

#define sz(x) (int((x).size()))

struct RT {
    struct node {
        int sum, left, right;
        node() : sum(0), left(0), right(0) {}
        node(const node &n) : sum(n.sum), left(n.left), right(n.right) {}
        node(int s, int l, int r) : sum(s), left(l), right(r) {}
    };

    std::vector<node> nodes;

    int newNode(node n = node()) {
        nodes.push_back(n);
        return sz(nodes) - 1;
    }

    int init(int nl, int nr) {
        int n = newNode();
        int nm = (nl+nr)/2;
        if (nl+1 < nr) {
            int l = init(nl, nm);
            nodes[n].left = l;
            int r = init(nm, nr);
            nodes[n].right = r;
        }
        return n;
    }

    int update(int old, int nl, int nr, int ui) {
        int now = newNode(nodes[old]);
        if (nl == ui && nl + 1 == nr) {
            nodes[now].sum++;
        } else {
            int nm = (nl+nr)/2;
            if (ui < nm) {
                int l = update(nodes[old].left, nl, nm, ui);
                nodes[now].left = l;
            } else {
                int r = update(nodes[old].right, nm, nr, ui);
                nodes[now].right = r;
            }
            nodes[now].sum = nodes[nodes[now].left].sum + nodes[nodes[now].right].sum;
        }
        return now;
    }

    int query(int now, int nl, int nr, int ql, int qr) {
        if (ql <= nl && nr <= qr) {
            return nodes[now].sum;
        } else {
            int sum = 0;
            int nm = (nl+nr)/2;
            if (ql < nm) sum += query(nodes[now].left, nl, nm, ql, qr);
            if (nm < qr) sum += query(nodes[now].right, nm, nr, ql, qr);
            return sum;
        }
    }
};

const int MaxC = 200*1000+5;

std::set<std::pair<int, int>> squares, vertices, hEdges, vEdges;
// these range trees are "horizontal" range trees over columns,
// sweeping vertically over rows over time
RT rtSquares, rtVertices, rtHEdges, rtVEdges;
int rootsSquares[MaxC], rootsVertices[MaxC], rootsHEdges[MaxC], rootsVEdges[MaxC];
int minr, maxr, minc, maxc;

void setupRT(RT &rt, int *roots, std::set<std::pair<int, int>> &points) {
    roots[0] = rt.init(0, MaxC);
    auto it = points.begin();
    for (int i = 0; i < MaxC; i++) {
        if (i) roots[i] = roots[i-1];
        while (it != points.end() && it->first == i) {
            roots[i] = rt.update(roots[i], 0, MaxC, it->second);
            it++;
        }
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    squares.emplace(sr, sc);
    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 /* S[i] == 'W' */ sc--;
        squares.emplace(sr, sc);
    }

    minr = minc = MaxC + 5;
    maxr = maxc = -5;

    for (auto &square : squares) {
        int r, c; std::tie(r, c) = square;

        minr = std::min(minr, r);
        minc = std::min(minc, c);
        maxr = std::max(maxr, r);
        maxc = std::max(maxc, c);

        vertices.emplace(r, c);
        vertices.emplace(r+1, c);
        vertices.emplace(r, c+1);
        vertices.emplace(r+1, c+1);

        hEdges.emplace(r, c);
        hEdges.emplace(r+1, c);
        vEdges.emplace(r, c);
        vEdges.emplace(r, c+1);
    }

    setupRT(rtSquares, rootsSquares, squares);
    setupRT(rtVertices, rootsVertices, vertices);
    setupRT(rtHEdges, rootsHEdges, hEdges);
    setupRT(rtVEdges, rootsVEdges, vEdges);
}

// both coordinates are [inclusive, inclusive]
int queryRT(RT &rt, int *roots, int ay, int by, int ax, int bx) {
    assert(ax-1 <= bx && ay <= by + 1);
    return rt.query(roots[by], 0, MaxC, ax, bx + 1) -
           rt.query(roots[ay-1], 0, MaxC, ax, bx + 1);
}

int colour(int ar, int ac, int br, int bc) {
    int V = /* internal vertices */
            queryRT(rtVertices, rootsVertices, ar+1, br, ac+1, bc) +
            /* external vertices */
            4 + 2 * (br - ar + bc - ac);
    int E = /* internal edges */
            queryRT(rtHEdges, rootsHEdges, ar+1, br, ac, bc) +
            queryRT(rtVEdges, rootsVEdges, ar, br, ac+1, bc) +
            /* external edges */
            2 * (br - ar + 1 + bc - ac + 1);
    // black faces
    int BF = /* internal faces */
             queryRT(rtSquares, rootsSquares, ar, br, ac, bc) +
             /* the infinite, external face */
             1;
    // components (because the outer black component might not be
    // connected to the original black component)
    int C = ((ac < minc && maxc < bc && ar < minr && maxr < br) ? 2 : 1);
    // white faces
    int WF = 1 + C - V + E - BF;
    return WF;
}

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