Submission #741469

#	Time	Username	Problem	Language	Result	Execution time	Memory
741469		phoebe	Painting Walls (APIO20_paint)	C++17	28 / 100	1589 ms	19148 KiB

paint

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

#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define PB push_back
#define FOR(i, n) for (int i = 0; i < n; i++)

const int maxn = 1e5 + 10, INF = 1e9 + 7;
int block = 224; // sqrt(m)
int n, m, k, c[maxn], tree[maxn * 4];
bool good[maxn] = {0};
set<int> pos[maxn];
set<int> can_paint[maxn];

void merge(set<int> &a, set<int> &b, int d){
    auto it = a.begin();
    while (it != a.end()){
        if (b.count((*it + d) % m) == 0) a.erase(it++);
        else it++;
    }
}

void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        tree[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
    tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}

int range(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (tl > r || tr < l) return INF;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return min(range(l, r, tl, tm, i * 2), 
    range(l, r, tm + 1, tr, i * 2 + 1));
}

int minimumInstructions(int N, int M, int K, 
vector<int> C, vector<int> A, vector<vector<int>> B){
    n = N, m = M, k = K; block = min(block, m);
    FOR(i, n) c[i] = C[i];
    FOR(i, m){
        FOR(j, A[i]) can_paint[B[i][j]].insert(i);
    }
    FOR(i, n){
        for (auto x : can_paint[c[i]]) pos[i].insert(x);
        for (int j = i + 1; j < min(n, i + block); j++){
            merge(pos[i], can_paint[c[j]], j - i);
        }
    }
    FOR(i, n - m + 1){
        int cur = i + block;
        while (cur + block - 1 < i + m){
            merge(pos[i], pos[cur], cur - i);
            cur += block;
        }
        while (cur < i + m){
            merge(pos[i], can_paint[c[cur]], cur - i);
        }
        if (pos[i].size() > 0) good[i] = true;
    }
    // FOR(i, n) cout << good[i] << ' '; cout << endl;
    if (!good[n - m]) return -1;
    fill(tree, tree + maxn * 4, INF);
    update(n - m, 1);
    for (int i = n - m - 1; i >= 0; i--){
        if (!good[i]) continue;
        int best = range(i, i + m);
        update(i, best + 1);
    }
    // FOR(i, n) cout << range(i, i) << ' '; cout << endl;
    int re = range(0, 0);
    return (re < INF ? re : -1);
}   

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