Submission #745374

#	Time	Username	Problem	Language	Result	Execution time	Memory
745374		Lobo	Painting Walls (APIO20_paint)	C++17	0 / 100	1 ms	212 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 1e9+10;

int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
    vector<int> f[k];
    for(int i = 0; i < m; i++) {
        sort(all(b[i]));
        for(auto x : b[i]) {
            f[x].pb(i);
        }
    }

    vector<pair<int,int>> pos;
    for(int i = n-1; i >= 0; i-= m) {
        for(auto j : f[c[i]]) {
            int cnt;
            int li = i;
            int lj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(li < 0 || b[lj].back() < c[li] || *lower_bound(all(b[lj]),c[li]) != c[li]) {
                    li++;
                    break;
                }
                li--;
                lj--;
                lj = (lj%m+m)%m;
            }

            int ri = i;
            int rj = j;
            cnt = 0;
            while(cnt++ <= m) {
                if(ri > n-1 || b[rj].back() < c[ri] || *lower_bound(all(b[rj]),c[ri]) != c[ri]) {
                    ri--;
                    break;
                }
                ri++;
                rj++;
                rj = (rj%m+m)%m;
            }
            pos.pb(mp(li,ri));
        }
    }

    sort(all(pos));

    vector<pair<int,int>> pos1;
    for(auto X : pos) {
        while(pos1.size() && pos1.back().fr == X.fr) pos1.pop_back();
        if(pos1.size() && pos1.back().sc >= X.sc) continue;
        pos1.pb(X);
    }
    swap(pos,pos1);
    reverse(all(pos));
    vector<int> dp(n+1,inf);
    for(int i = 0; i+m <= n; i++) {
        if(dp[i] == inf) continue;
        while(pos.size() && pos.back().sc < i+m-1) pos.pop_back();
        if(pos.empty() || pos.back().fr > i) continue;
        dp[i+m] = dp[i]+1;
    }

    if(dp[n] == inf) return -1;
    return dp[n];
}

        

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