Submission #569374

#	Time	Username	Problem	Language	Result	Execution time	Memory
569374		tranxuanbach	Painting Walls (APIO20_paint)	C++17	100 / 100	427 ms	24064 KiB

paint

#ifndef FEXT

#include "paint.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5, M = 5e4 + 5, K = 1e5 + 5, F = sqrt(4e5) + 5, LN = 17;

int n, m, k;
int a[N];
vi b[M];

vi rb[K]; // rb[i] = {j such that b[j] contains i}
bool c[N]; // c[i] = 1 if there exist a valid instruction (x, y = i - m + 1)
int dp[N][LN];

int dp_range_min(int l, int r){
    if (l > r){
        return N;
    }
    int z = __lg(r - l + 1);
    return min(dp[l + (1 << z) - 1][z], dp[r][z]);
}

int prev(int i){
    return i == 1 ? m : i - 1;
}

int next(int i){
    return i == m ? 1 : i + 1;
}

int minimumInstructions(int _n, int _m, int _k, vi _c, vi _a, vvi _b){
    n = _n; m = _m; k = _k;
    ForE(i, 1, n){
        a[i] = _c[i - 1];
    }
    ForE(j, 1, m){
        b[j] = _b[j - 1];
    }

    ForE(j, 1, m){
        Fora(i, b[j]){
            rb[i].emplace_back(j);
        }
    }
    for (int anchor = m; anchor <= n; anchor += m){
        Fora(j, rb[a[anchor]]){
            int l = anchor, r = anchor;
            int jl = j, jr = j;
            while (l - 1 > anchor - m){
                if (binary_search(bend(b[prev(jl)]), a[l - 1])){
                    l--;
                    jl = prev(jl);
                }
                else{
                    break;
                }
            }
            while (r + 1 < anchor + m and r + 1 <= n){
                if (binary_search(bend(b[next(jr)]), a[r + 1])){
                    r++;
                    jr = next(jr);
                }
                else{
                    break;
                }
            }
            ForE(i, l + m - 1, r){
                c[i] = 1;
            }
        }
    }
    dp[0][0] = 0;
    For(j, 1, LN){
        if (0 - (1 << (j - 1)) >= 0){
            dp[0][j] = min(dp[0][j - 1], dp[0 - (1 << (j - 1))][j - 1]);
        }
    }
    ForE(i, 1, n){
        dp[i][0] = N;
        if (c[i]){
            dp[i][0] = min(dp[i][0], dp_range_min(max(0, i - m), i - 1) + 1);
        }
        For(j, 1, LN){
            if (i - (1 << (j - 1)) >= 0){
                dp[i][j] = min(dp[i][j - 1], dp[i - (1 << (j - 1))][j - 1]);
            }
        }
    }
    return (dp[n][0] == N ? -1 : dp[n][0]);
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int N, M, K;
    assert(3 == scanf("%d %d %d", &N, &M, &K));

    std::vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &C[i]));
    }

    std::vector<int> A(M);
    std::vector<std::vector<int>> B(M);
    for (int i = 0; i < M; ++i) {
        assert(1 == scanf("%d", &A[i]));
        B[i].resize(A[i]);
        for (int j = 0; j < A[i]; ++j) {
            assert(1 == scanf("%d", &B[i][j]));
        }
    }

    int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
    printf("%d\n", minimum_instructions);

    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
--------------------------------------------------|
5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
--------------------------------------------------|
-1
--------------------------------------------------|
==================================================+
*/

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