Submission #549619

#	Time	Username	Problem	Language	Result	Execution time	Memory
549619		smax	Land of the Rainbow Gold (APIO17_rainbow)	C++17	24 / 100	245 ms	125784 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e7 + 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;
}

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