Submission #1142189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142189		mnbvcxz123	Painting Walls (APIO20_paint)	C++20	100 / 100	153 ms	23400 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 100'000;
const int M = 17;
const int INF = 1'000'000'000;

int n, m, k, c[N + 10], good[N + 10];
int dp[2][N + 10], ans[N + 10], rmq[N + 10][M + 3];
vector<int> pack[N + 10];

void readInput(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    n = N;
    m = M;
    k = K;
    for (int i = 0; i < n; i++)
        c[i] = C[i];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < A[i]; j++)
            pack[B[i][j]].push_back(i);
    //cout << "size Pack " << pack[0].size() << ' ' << pack[1].size() << ' ' << pack[2].size() << endl;
}

void delDP(int idx) {
    if (idx > n)
        return;
    for (auto x: pack[c[idx]])
        dp[idx % 2][x] = 0;
}

void calcGood() {
    for (int i = n - 1; i >= 0; i--) {
        int t = i % 2;
        delDP(i + 2);
        for (auto x: pack[c[i]]) {
            dp[t][x] = dp[t ^ 1][(x + 1) % m] + 1;
            good[i] |= (dp[t][x] >= m);
            //cout << i << ' ' << c[i] << ", " << x << " -> " << dp[t][x] << endl;
        }
        //cout << i << ": " << good[i] << endl;
    }
}

void updateRMQ(int i) {
    rmq[i][0] = ans[i];
    for (int j = 1; j <= M; j++)
        if (i + (1 << j) <= n)
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}

int get(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return min(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
}

void calcAns() {
    for (int i = n - 1; i > n - m; i--) {
        ans[i] = INF;
        updateRMQ(i);
    }
    for (int i = n - m; i >= 0; i--) {
        if (good[i])
            ans[i] = min(INF, get(i + 1, i + m) + 1);
        else
            ans[i] = INF;
        updateRMQ(i);
    }
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    readInput(N, M, K, C, A, B);
    calcGood();
    calcAns();
    return (ans[0] == INF? -1: ans[0]);
}

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