# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
395854 | khangal | Painting Walls (APIO20_paint) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double db;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
#define pb push_back
#define po pop_back
#define ff first
#define ss second
#define MIN -1e18
#define MAX 1e18
#define lw lower_bound
#define SZ(_a) (ll)_a.size()
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,mid,mn,T,sum,c[1234567],h1,h2,x,y,z,l,r,cnt,cnt1,ans;
vector<ll> vec[1234567];
bool ok[1234567],ok1;
int minimumInstructions(
ll minimumInstructions(ll n,ll m,ll k,vector<ll> color,vector<ll> a,vector<vector<ll> > b){
vector<vector<ll> > loc(k);
for(int i=0;i<m;i++){
for(int j=0;j<SZ(b[i]);j++)loc[b[i][j]].pb(i);
}
vector<vector<ll> > it(m);
for(int i=0;i<n;i++){
for(int j:loc[color[i]]){
it[((j-i)%m+m)%m].pb(i);
}
}
vector<ll> r(n);
for(const auto &v:it){
ll lst=n+1,len=0;
for(int i=SZ(v)-1;i>=0;i--){
if(v[i]+1!=lst)len=0;
++len;
r[v[i]]=max(r[v[i]],len);
lst=v[i];
}
}
vector<ll> lis;
for(int i=0;i<n;i++)if(r[i]>=m)lis.pb(i);
ll ans=0;
for(int R=0,id=0;R<n;){
while(id<SZ(lis)&&lis[id]<=R)++id;
if(id==0)return -1;
ll L=lis[id-1];
if(L+m<=R)return -1;
++ans;
R=L+m;
}
return ans;
}