oj.uz

Submission #908988

# Submission time Handle Problem Language Result Execution time Memory
908988 2024-01-17T04:16:58 Z wii Painting Walls (APIO20_paint) C++17
0 / 100
 2 ms 9308 KB 
#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];

    foru(i, 1, N) {
        for (int u: f0[i - 1]) used[u] = true;

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

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

    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;
    }

    foru(i, M, N) {
        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;
    }

    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 + 1, N + 1);
    if (ans == Inf) ans = -1;

    return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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