Submission #949635

#	Time	Username	Problem	Language	Result	Execution time	Memory
949635		Aiperiii	Painting Walls (APIO20_paint)	C++14	100 / 100	284 ms	10392 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A, vector<vector<int>> B) {
    vector <int> l(N),r(N),pr(N);
    for(int i=0;i<N;i++){
        int pos=i;
        for(int j=0;j<min(M,N-i);j++){
            auto it=lower_bound(all(B[j]),C[pos]);
            if(it!=B[j].end() && *it==C[pos]){
                pos++;r[i]++;
            }
            else break;
        }
    }
    for(int i=N-1;i>=0;i--){
        int pos=i;
        for(int j=M-1;j>=max(0,M-i-1);j--){
            auto it=lower_bound(all(B[j]),C[pos]);
            if(it!=B[j].end() && *it==C[pos]){
                pos--;l[i]++;
            }
            else break;
        }
    }
    for(int i=0;i<N;i++){
        int st1=i,st2=i-M+r[i];
        if(i-1>=0)st1-=l[i-1];
        if(st1<=st2){
            pr[st1]++;
            if(st2+1<N)pr[st2+1]--;
        }
    }
    vector <int> v;
    for(int i=0;i<N;i++){
        if(i-1>=0)pr[i]+=pr[i-1];
        if(pr[i]>0)v.pb(i);
    }
    int st=0,ans=0;
    while(st!=N){
        auto it=lower_bound(all(v),st);
        if(it!=v.end() && *it==st){
            st+=M;ans++;
        }
        else if(it!=v.begin()){
            it--;
            if(*it+M>st){
                st=*it+M;ans++;
            }
            else {
                ans=-1;break;
            }
        }
        else{
            ans=-1;break;
        }
        
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector <int> c(n),a(m);
    for(int i=0;i<n;i++)cin>>c[i];
    for(int i=0;i<m;i++)cin>>a[i];
    vector <vector <int> > b(m);
    for(int i=0;i<m;i++){
        for(int j=0;j<a[i];j++){
            int x;
            cin>>x;
            b[i].pb(x);
        }
    }
    cout<<minimumInstructions(n,m,k,c,a,b)<<"\n";
}*/
/*

8 3 5
3 3 1 3 4 4 2 2
3 2 2
0 1 2
2 3
3 4
 
5 4 4
1 0 1 2 2
2 1 1 1
0 1
1
2
3

*/

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