Submission #319492

#	Time	Username	Problem	Language	Result	Execution time	Memory
319492		VEGAnn	Painting Walls (APIO20_paint)	C++14	100 / 100	1198 ms	32740 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ft first
using namespace std;
using namespace __gnu_pbds;
const int M = 50100;
const int N = 100100;
const int K = 100100;
const int oo = 2e9;
gp_hash_table<int, bool> inside[K];
int f[N], cnt[M], st[4 * N];

void build(int v, int l, int r){
    if (l == r){
        st[v] = f[l];
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r){
    if (l > r) return oo;

    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    return min(get(v + v, tl, md, l, min(r, md)),
               get(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

void update(int v, int l, int r, int ps){
    if (l == r){
        st[v] = f[l];
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps);
    else update(v + v + 1, md + 1, r, ps);

    st[v] = min(st[v + v], st[v + v + 1]);
}

int minimumInstructions(int n, int m, int k, std::vector<int> C,
                         std::vector<int> A, std::vector<std::vector<int>> B) {

    for (int i = 0; i < m; i++)
    for (int j = 0; j < A[i]; j++)
        inside[B[i][j]][i] = 1;

    int ptr = 0;

    for (int i = n - 1; i > n - m; i--){
        for (auto cr : inside[C[i]]){
            int loc = (ptr + cr.ft);

            if (loc >= m)
                loc -= m;

            cnt[loc]++;
        }

        ptr++;

        if (ptr == m) ptr = 0;
    }

    f[n] = 0;

    fill(f, f + n, oo);

    build(1, 0, n);

    for (int i = n - m; i >= 0; i--){
        int mn = get(1, 0, n, i + 1, i + m);

        if (mn == oo) break;

        if (i + m < n){
            for (auto cr : inside[C[i + m]]){
                int loc = (ptr + cr.ft);

                if (loc >= m)
                    loc -= m;

                cnt[loc]--;
            }
        }

        bool ok = 0;

        for (auto cr : inside[C[i]]){
            int loc = (ptr + cr.ft);

            if (loc >= m)
                loc -= m;

            cnt[loc]++;

            if (cnt[loc] == m) ok = 1;
        }

        if (ok) {
            f[i] = mn + 1;
            update(1, 0, n, i);
        }

        ptr++;

        if (ptr == m) ptr = 0;
    }

    return (f[0] == oo ? -1 : f[0]);
}

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