Submission #1105097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105097		ByeWorld	Painting Walls (APIO20_paint)	C++14	100 / 100	261 ms	32848 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 5e5+15;
const int INF = 1e9+10;
const int LOG = 19;
const int MOD = 1e9+7;

int n, m, k;
int c[MAXN], a[MAXN];
vector <int> have[MAXN];
int dp[MAXN], cnt[MAXN], numcan;

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	n = N; m = M; k = K;
	int te = (n+m-1)/m * m;
	for(int i=1; i<=n; i++) c[i] = C[i-1];
	for(int i=1; i<=m; i++){
		a[i] = A[i-1];
		for(auto in : B[i-1]) have[in].pb(i);
	}
	dp[0] = 0;
	for(int i=1; i<=n; i++) dp[i] = INF;

	for(int i=1; i<=m-1; i++){
		int val = c[i];
		for(auto in : have[val]){
			int idx = (in-i+te+m)%m;
			cnt[idx]++;
		}
	}
	multiset <int> mu; 
	for(int i=0; i<=m-1; i++) mu.insert(dp[i]);
	for(int i=m; i<=n; i++){
		int val = c[i];
		for(auto in : have[val]){
			int idx = (in-i+te+m)%m;
			cnt[idx]++;
			if(cnt[idx] == m) numcan++;
		}
		if(i != m){
			val = c[i-m];
			for(auto in : have[val]){
				int idx = (in-i+te+m)%m;
				cnt[idx]--;
				if(cnt[idx] == m-1) numcan--;
			}
		}

		if(i-m-1 >= 0) mu.erase(mu.find(dp[i-m-1]));
		if(!mu.empty() && numcan != 0) dp[i] = (*mu.begin())+1;
		mu.insert(dp[i]);
		// cout << i << ' ' << numcan << ' ' << dp[i] << " umcan\n";
	}
	return (dp[n]>n ? -1 : dp[n]);
}

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