Submission #560959

#	Time	Username	Problem	Language	Result	Execution time	Memory
560959		nghiass001	Painting Walls (APIO20_paint)	C++17	100 / 100	324 ms	20152 KiB

paint

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)

using namespace std;
using namespace __gnu_pbds;

template <class key, class value>
using ordered_map = tree<key, value, less<key>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100005, maxM = 50005, logM = 16, maxK = 100005, INF = 0x3c3c3c3c;
int kmp[maxM], kmp2[maxM], prefix[N], suffix[N], ans[N];
int p[maxM][logM];
vector<int> Q[maxK];
map<int, int> M[maxM], M_next[maxM];

int avail[N], num[N], maxL[N];

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B) {
    C.insert(C.begin(), -1);

    FOR(i, 1, m) {
        for(int v : B[i - 1]) {
            Q[v].push_back(i);
        }
    }

    vector<pair<int, int>> List;
    FOR(i, 1, n) {
        for(int v : Q[C[i]]) {
            if (avail[(v == 1 ? m : v - 1)] == i - 1) {
                List.emplace_back(v, num[(v == 1 ? m : v - 1)] + 1);
            }
            else {
                List.emplace_back(v, 1);
            }
        }
        for(auto [v, val] : List) {
            avail[v] = i;
            num[v] = val;
            maxL[i] = max(maxL[i], val);
        }
        List.clear();
    }
    deque<int> DQ;
    DQ.push_back(0);
    FOR(i, m, n) {
        while (!DQ.empty() && DQ.front() < i - m) DQ.pop_front();
        if (DQ.empty()) return -1;
        if (maxL[i] >= m) ans[i] = ans[DQ.front()] + 1, DQ.push_back(i);
    }
    if (ans[n] == 0) return -1;
    return ans[n];
}

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