Submission #1140803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140803		anmattroi	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	372 ms	332500 KiB

rainbow

/**
Task: APIO17_rainbow (Land of the Rainbow Gold)
Link: https://oj.uz/problem/view/APIO17_rainbow
**/
#include <bits/stdc++.h>
#include "rainbow.h"
#define maxr 200005
#define maxc 200005
#define maxq 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;


int r, c;


struct persistent_tree {
    vector<int> it, L, R, root;
    int nt = 0;

    int build(int lo, int hi) {
        if (lo == hi) return ++nt;
        int mid = (lo + hi) >> 1, cur = ++nt;
        L[cur] = build(lo, mid);
        R[cur] = build(mid+1, hi);
        return cur;
    }

    void init(int r, int c, int m) {
        root.assign(r+1, 0);
        it.assign(20*(m+r) + 2*c, 0);
        L .assign(20*(m+r) + 2*c, 0);
        R .assign(20*(m+r) + 2*c, 0);
        root[0] = build(1, c);
    }

    int upd(int u, int oldver, int lo, int hi) {
        if (lo == hi) {
            it[++nt] = it[oldver] + 1;
            return nt;
        }
        int cur = ++nt, mid = (lo + hi) >> 1;
        if (u <= mid) {
            L[cur] = upd(u, L[oldver], lo, mid);
            R[cur] = R[oldver];
        } else {
            L[cur] = L[oldver];
            R[cur] = upd(u, R[oldver],mid+1,hi);
        }
        it[cur] = it[L[cur]] + it[R[cur]];
        return cur;
    }

    int get(int u, int v, int r, int lo, int hi) {
        if (u > hi || v < lo) return 0;
        if (u <= lo && hi <= v) return it[r];
        int mid = (lo + hi) >> 1;
        return get(u, v, L[r], lo, mid) + get(u, v, R[r], mid+1, hi);
    }

} tree_horizontal, tree_vertical, tree, tree_vertice;

int query_horizontal(int x, int y, int u, int v) {
    if (x > u || y > v) return 0;
    return tree_horizontal.get(y, v, tree_horizontal.root[u], 1, c) -
           tree_horizontal.get(y, v, tree_horizontal.root[x-1], 1, c);
}

int query_vertical(int x, int y, int u, int v) {
    if (x > u || y > v) return 0;
    return tree_vertical.get(y, v, tree_vertical.root[u], 1, c+1) -
           tree_vertical.get(y, v, tree_vertical.root[x-1], 1, c+1);
}

int query(int x, int y, int u, int v) {
    if (x > u || y > v) return 0;
    return tree.get(y, v, tree.root[u], 1, c)
        -  tree.get(y, v, tree.root[x-1], 1, c);
}

int query_vertice(int x, int y, int u, int v) {
    if (x > u || y > v) return 0;
    return tree_vertice.get(y, v, tree_vertice.root[u], 1, c+1)
        - tree_vertice.get(y, v, tree_vertice.root[x-1],1, c+1);
}

int colour(int ar, int ac, int br, int bc) {
    int E = query_horizontal(ar+1, ac, br, bc) +
            query_vertical(ar, ac+1, br, bc)
            + 2 * (br-ar+2) + 4 * (br-ar+1)
            + 2 * (bc-ac+2) + 4 * (bc-ac+1);

    int V = query_vertice(ar+1, ac+1, br, bc)
            + 4 * (br-ar+2) + 4 * (bc-ac+2) - 4;
    int R = query(ar, ac, br, bc);
    int C;
    if (R == 0) C = 1;
    else {
        C = (R - query(ar+1, ac+1, br-1, bc-1) > 0 ? 1 : 2);
    }
    int F = E - V + 1 + C;
    R += 2 * (br-ar+1) + 2 * (bc-ac+1);
    int A = F - (R+1);
    return A;
}

//F = E - V + 1 + C

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R;
    c = C;
    set<ii> hl, vl, p, vertices;
    hl.insert(ii{sr+1, sc});
    hl.insert(ii{sr  , sc});
    vl.insert(ii{sr, sc+1});
    vl.insert(ii{sr, sc  });
    p.insert(ii{sr, sc});
    vertices.insert(ii{sr, sc});
    vertices.insert(ii{sr+1, sc});
    vertices.insert(ii{sr, sc+1});
    vertices.insert(ii{sr+1, sc+1});
    tree_horizontal.init(r+1, c, M+1);
    tree_vertical  .init(r, c+1, M+1);
    tree           .init(r, c, M+1);
    tree_vertice   .init(r+1, c+1, M+1);

    for (int i = 0; i < M; i++) {
        char ch = S[i];
        switch (ch) {
        case 'N':
            --sr;
            break;
        case 'W':
            --sc;
            break;
        case 'S':
            ++sr;
            break;
        case 'E':
            ++sc;
            break;
        }
        p.insert(ii{sr, sc});
        hl.insert(ii{sr+1, sc});
        hl.insert(ii{sr  , sc});
        vl.insert(ii{sr, sc+1});
        vl.insert(ii{sr, sc  });
        vertices.insert(ii{sr, sc});
        vertices.insert(ii{sr+1, sc});
        vertices.insert(ii{sr, sc+1});
        vertices.insert(ii{sr+1, sc+1});
    }

    int it;


    it = 1;
    for (auto [u, v] : hl) {
        while (it <= u) {tree_horizontal.root[it] = tree_horizontal.root[it-1]; ++it;}
        tree_horizontal.root[u] = tree_horizontal.upd(v, tree_horizontal.root[u], 1, c);
    }
    while (it <= r+1) {
        tree_horizontal.root[it] = tree_horizontal.root[it-1];
        ++it;
    }

    it = 1;
    for (auto [u, v] : vl) {
        while (it <= u) {tree_vertical.root[it] = tree_vertical.root[it-1]; ++it;}
        tree_vertical.root[u] = tree_vertical.upd(v, tree_vertical.root[u], 1, c+1);
    }
    while (it <= r) {
        tree_vertical.root[it] = tree_vertical.root[it-1];
        ++it;
    }

    it = 1;
    for (auto [u, v] : p) {
        while (it <= u) {tree.root[it] = tree.root[it-1]; ++it;}
        tree.root[u] = tree.upd(v, tree.root[u], 1, c);
    }
    while (it <= r) {
        tree.root[it] = tree.root[it-1];
        ++it;
    }

    it = 1;
    for (auto [u, v] : vertices) {
        while (it <= u) {tree_vertice.root[it] = tree_vertice.root[it-1]; ++it;}
        tree_vertice.root[u] = tree_vertice.upd(v, tree_vertice.root[u], 1, c+1);
    }
    while (it <= r+1) {
        tree_vertice.root[it] = tree_vertice.root[it-1];
        ++it;
    }
}

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