Submission #361636

#	Time	Username	Problem	Language	Result	Execution time	Memory
361636		MvC	Painting Walls (APIO20_paint)	C++11	100 / 100	678 ms	502764 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int i,l,j,ps[nmax],rs,mx,nx,p;
vector<pair<int,int> >cl[nmax],col[nmax];
int minimumInstructions(int n,int m,int k,vector<int> c,vector<int> b,vector<vector<int> > a)
{
    for(i=0;i<m;i++)for(j=0;j<b[i];j++)col[a[i][j]].pb(mkp(i,0));
    for(i=0;i<k;i++)sort(all(col[i]));
    for(i=0;i<n;i++)
    {
        cl[i]=col[c[i]];
        p=0;
        for(j=0;j<lun(cl[i]);j++)
        {
            l=(cl[i][j].fr-1+m)%m;
            cl[i][j].sc=i;
            if(i)
            {
                if(l!=m-1)
                {
                    for(;p<lun(cl[i-1]);p++)if(cl[i-1][p].fr>=l)break;
                    if(p<lun(cl[i-1]) && cl[i-1][p].fr==l)cl[i][j].sc=cl[i-1][p].sc;
                }
                else if(!cl[i-1].empty() && cl[i-1].back().fr==l)cl[i][j].sc=cl[i-1].back().sc;
            }
            if(i-cl[i][j].sc+1>=m)ps[i-m+1]=1;
        }
    }
    mx=-m;
    for(i=0;i<n;i++)
    {
        if(ps[i])mx=i;
        if(nx==i)
        {
            if(mx+m-1>=i)
            {
                rs++;
                nx=mx+m;
            }
            else
            {
                rs=-1;
                break;
            }
        }
    }
    return rs;
}
/*int main()
{
    //freopen("sol.in","r",stdin);
    //freopen("sol.out","w",stdout);
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 0;
}*/

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