Submission #1133981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133981		imarn	Painting Walls (APIO20_paint)	C++20	100 / 100	320 ms	255296 KiB

paint

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5,inf=1e9;
int mdp[mxn]{0};
vector<int>g[mxn];
vector<int>dp[mxn];
int n,m,k;
int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
    n=N,m=M,k=K;
    for(int i=0;i<m;i++){
        for(auto it : B[i])g[it].pb(i);
    }for(int i=0;i<k;i++)sort(all(g[i]));
    dp[0].resize(g[C[0]].size(),0);
    for(int i=0;i<dp[0].size();i++)dp[0][i]=1;mdp[0]=1;
    for(int i=1;i<n;i++){
        dp[i].resize(g[C[i]].size(),0);
        int cr=0;
        for(int j=0;j<g[C[i]].size();j++){
            while(cr<g[C[i-1]].size()&&g[C[i-1]][cr]+1<g[C[i]][j])cr++;
            if(cr<g[C[i-1]].size()&&g[C[i-1]][cr]+1==g[C[i]][j])dp[i][j]=max(dp[i][j],dp[i-1][cr]+1);
            else dp[i][j]=1;
            mdp[i]=max(mdp[i],dp[i][j]);
        }
        if(!g[C[i-1]].empty()&&!g[C[i]].empty()&&g[C[i-1]].back()==m-1&&g[C[i]][0]==0)dp[i][0]=max(dp[i][0],dp[i-1].back()+1),mdp[i]=max(mdp[i],dp[i][0]);
    }int ans=inf;
    deque<pii>dq;dq.pb({-1,0});
    for(int i=m-1;i<n;i++){
        while(!dq.empty()&&i-dq.front().f>m)dq.pop_front();
        int rs=inf;
        if(mdp[i]>=m&&!dq.empty()){rs=1+dq.front().s;
            while(!dq.empty()&&dq.back().s>rs)dq.pop_front();
            dq.pb({i,rs});
        }ans=rs;
    }return (ans==1e9?-1:ans);
}

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