Submission #395859

#	Time	Username	Problem	Language	Result	Execution time	Memory
395859		khangal	Painting Walls (APIO20_paint)	C++14	100 / 100	1366 ms	290676 KiB

paint

#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
#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;	
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;
	
}

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