Submission #1272180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272180		StefanSebez	Painting Walls (APIO20_paint)	C++20	0 / 100	1 ms	576 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,inf=1e9;
int n,m,K;
bool desno[N];
bool imac[510][510];
int dp[2][N],now=1,pre;
vector<int>clr[2];
struct SegTree{
    int root,nc,lc[2*N],rc[2*N],maks[2*N];
    SegTree(){maks[0]=inf;}
    void Update(int &c,int ss,int se,int qind,int qval){
        if(!c)c=++nc;
        if(ss==se){maks[c]=qval;return;}
        int mid=ss+se>>1;
        if(qind<=mid)Update(lc[c],ss,mid,qind,qval);
        else Update(rc[c],mid+1,se,qind,qval);
        maks[c]=min(maks[lc[c]],maks[rc[c]]);
    }
    int Get(int c,int ss,int se,int qs,int qe){
        if(qs>qe||qe<ss||se<qs)return inf;
        if(qs<=ss&&se<=qe)return maks[c];
        int mid=ss+se>>1;return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST;
int minimumInstructions(int n1,int m1,int K1,vector<int>C,vector<int>A,vector<vector<int>>colors) {
    n=n1,m=m1,K=K1;
    vector<int>ids[K+1];
    for(int i=0;i<m;i++){
        sort(colors[i].begin(),colors[i].end());
        for(auto j:colors[i]) ids[j].pb(i);
    }
    /*for(int i=0;i<m;i++){
        for(auto j:colors[i]) imac[i][j]=true;
    }*/
    for(int i=n-1;i>=0;i--){
        swap(now,pre);
        //for(int j=0;j<m;j++) dp[now][j]=0;
        for(auto j:clr[now]) clr[now][j]=0;
        clr[now].clear();
        int maks=0;
        for(auto j:ids[C[i]]){
            dp[now][j]=max(dp[now][j],dp[pre][(j+1)%m]+1);
            maks=max(maks,dp[now][j]);
            clr[now].pb(j);
        }
        if(maks>=m) desno[i]=true;
    }
    /*for(int y=0;y<=n-m;y++){
        for(int x=0;x<m;x++){
            //printf("%i %i\n",x,y);
            bool moze=true;
            for(int l=0;l<m;l++){
                //int lb=lower_bound(colors[(x+l)%m].begin(),colors[(x+l)%m].end(),C[y+l])-colors[(x+l)%m].begin();
                //if(!(lb<colors[(x+l)%m].size()&&colors[(x+l)%m][lb]==C[y+l])) moze=false;
                if(!imac[(x+l)%m][C[y+l]]){moze=false;break;}
            }
            if(moze){desno[y]=true;break;}
        }
    }*/
    //for(int i=0;i<n;i++) cout<<desno[i]<<" ";cout<<endl;
    int dp[n+10]={0};
    for(int i=0;i<=n;i++) dp[i]=inf;
    dp[n]=0;ST.Update(ST.root,0,n,n,0);
    for(int i=n-1;i>=0;i--){
        if(!desno[i]) continue;
        dp[i]=ST.Get(ST.root,0,n,i,min(i+m,n))+1;
        ST.Update(ST.root,0,n,i,dp[i]);
        /*for(int j=i+1;j<=min(i+m,n);j++){
            dp[i]=min(dp[i],dp[j]+1);
        }*/
    }
    int res=dp[0];
    if(res>=inf) res=-1;
    return res;
}

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