Submission #1166014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166014		wii	벽 칠하기 (APIO20_paint)	C++17	28 / 100	755 ms	589824 KiB

paint

// #define local

#ifndef local
    #include "paint.h"
#endif


#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], a[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 + 1);

    for (int i = 1; i <= N; ++i)
        a[i] = C[i - 1];

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

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

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

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

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

        if (!ok[i]) {
            for (int u: f[a[i]]) if (u > 1) {
                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;
}

#ifdef local
signed main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> C(n);
    for (int &x: C) cin >> x;

    vector<int> A(m);
    vector<vector<int>> B;

    for (int i = 1; i <= m; ++i) {
        cin >> A[i - 1];

        B.emplace_back();
        B.back().resize(A[i - 1]);
        
        for (int &x: B.back())
            cin >> x;
    }

    int ans = minimumInstructions(n, m, k, C, A, B);
    cout << ans << endl;
}
#endif

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