Submission #1166021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166021		wii	Painting Walls (APIO20_paint)	C++17	0 / 100	4 ms	8260 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;
vector<int> f0[N], fn[N];
vector<int> adj[N];
int a[N], used[N], ok[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 minimumInstructions(int N, int M, int K, std::vector<int> _C, std::vector<int> A, std::vector<std::vector<int>> B) {
    n = N + 1;

    foru(i, 0, M - 1) {
        foru(j, 0, A[i] - 1)
            adj[B[i][j]].push_back(i + 1);
    }

    foru(i, 1, N)
        a[i] = _C[i - 1];

    ford(i, N, 1) {
        for (int u: fn[i + 1]) used[u] = true;

        for (int u: adj[a[i]]) {
            if (u == M) fn[i].push_back(u); else
                if (used[u + 1]) fn[i].push_back(u);
        }

        for (int u: fn[i + 1]) used[u] = false;
    }

    vector<int> cur, prv;
    foru(i, 1, N) {
        for (int u: prv) used[u] = true;

        for (int u: adj[a[i]]) {
            if (u == 1) cur.push_back(u); else
                if (used[u - 1]) cur.push_back(u);
        }

        for (int u: prv) used[u] = false;

        if (i >= M) {
            for (int u: f0[i]) used[u] = true;

            ok[i] = (used[M] == true);
            for (int u: fn[i - M + 1]) {
                ok[i] |= (used[u - 1]);
            }

            for (int u: f0[i]) used[u] = false;
        }

        prv.clear();
        swap(prv, cur);
    }

    St.upd(0, 0);
    foru(i, M, N) if (ok[i]) {
        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: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37