Submission #1166013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166013		wii	Painting Walls (APIO20_paint)	C++17	28 / 100	715 ms	589824 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)

const int N = 1e5 + 5;
int n;

const int Inf = 0x3f3f3f3f;

struct SegmentTree {
    int f[N * 2];

    SegmentTree() {
        memset(f, 0x3f, sizeof f);
    }

    void upd(int u, int x) {
        ++u;
        for (f[u += n] = x; u > 1; u >>= 1)
            f[u >> 1] = min(f[u], f[u ^ 1]);
    }

    int get(int l, int r) {
        int ans = Inf;

        ++l; ++r;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans = min(ans, f[l++]);
            if (r & 1) ans = min(ans, f[--r]);
        }
        return ans;
    }
};

SegmentTree St;
int ok[N];
vector<int> f[N];
set<int> lf[N], rf[N];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    n = N + 1;

    for (int i = 0; i < M; ++i)
        sort(all(B[i]));

    for (int i = 0; i < M; ++i) for (int u: B[i])
        f[u].push_back(i);


    for (int i = 1; i <= N; ++i) {
        for (int u: lf[i - 1]) if (u + 1 < M) {
            if (binary_search(all(B[u + 1]), C[i - 1]))
                lf[i].insert(u + 1);
        }

        if (binary_search(all(B[0]), C[i - 1]))
            lf[i].insert(0);
    }

    for (int i = N; i >= 1; --i) {
        for (int u: rf[i + 1]) if (u > 0) {
            if (binary_search(all(B[u - 1]), C[i - 1]))
                rf[i].insert(u - 1);
        }

        if (binary_search(all(B[M - 1]), C[i - 1]))
            rf[i].insert(M - 1);
    }

    for (int i = 1; i <= N; ++i) {
        ok[i] = rf[i].find(0) != rf[i].end();

        if (!ok[i]) {
            for (int u: f[C[i - 1]]) if (u != 0) {
                ok[i] |= (rf[i].find(u) != rf[i].end()) & (lf[i + M - 1].find(u - 1) != lf[i + M - 1].end());
                if (ok[i]) break;
            }
        }
    }

    St.upd(0, 0);
    for (int i = M; i <= N; ++i) if (ok[i - M + 1]) {
        St.upd(i, St.get(i - M, i - 1) + 1);
    }

    int ans = St.get(N, N);
    if (ans == Inf) ans = -1;

    return ans;
}

• Subtask 1: 0 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37