oj.uz

Submission #549619

# Submission time Handle Problem Language Result Execution time Memory
549619 2022-04-16T07:07:18 Z smax Land of the Rainbow Gold (APIO17_rainbow) C++17
24 / 100
 245 ms 125784 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 192 ms 125004 KB Output is correct
3 Correct 136 ms 124248 KB Output is correct
4 Correct 109 ms 124984 KB Output is correct
5 Correct 112 ms 98276 KB Output is correct
6 Correct 57 ms 36588 KB Output is correct
7 Correct 71 ms 52920 KB Output is correct
8 Correct 139 ms 102272 KB Output is correct
9 Correct 127 ms 91208 KB Output is correct
10 Correct 47 ms 32776 KB Output is correct
11 Correct 76 ms 64620 KB Output is correct
12 Correct 245 ms 125004 KB Output is correct
13 Correct 127 ms 124180 KB Output is correct
14 Correct 100 ms 125076 KB Output is correct
15 Correct 115 ms 98252 KB Output is correct
16 Correct 41 ms 33172 KB Output is correct
17 Correct 86 ms 53012 KB Output is correct
18 Correct 168 ms 125004 KB Output is correct
19 Correct 152 ms 125712 KB Output is correct
20 Correct 163 ms 125600 KB Output is correct
21 Correct 146 ms 102248 KB Output is correct
22 Correct 139 ms 91132 KB Output is correct
23 Correct 39 ms 32792 KB Output is correct
24 Correct 77 ms 64700 KB Output is correct
25 Correct 193 ms 125068 KB Output is correct
26 Correct 137 ms 124064 KB Output is correct
27 Correct 118 ms 125048 KB Output is correct
28 Correct 108 ms 98276 KB Output is correct
29 Correct 39 ms 33100 KB Output is correct
30 Correct 94 ms 53004 KB Output is correct
31 Correct 159 ms 125096 KB Output is correct
32 Correct 157 ms 125784 KB Output is correct
33 Correct 153 ms 125644 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -