Submission #291692

#	Time	Username	Problem	Language	Result	Execution time	Memory
291692		nvmdava	Painting Walls (APIO20_paint)	C++17	100 / 100	400 ms	13304 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int r[100005], l[100005];
int pos[100005];
vector<int> col[100005];
int la[100005];
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	
	for(int i = 0; i < M; ++i)
		for(int& j : B[i])
			col[j].push_back(i);

	for(int i = 1; i <= N; ++i){
		for(int& x : col[C[i - 1]]){
			if(i > x && i - x + r[i - x] == i){
				++r[i - x];
			}
		}
	}

	for(int i = N; i >= 1; --i){
		for(int& x : col[C[i - 1]]){
			if(i + M - 1 - x <= N && i + M - 1- x - l[i + M - 1 - x] == i){
				++l[i + M - 1 - x];
			}
		}
	}

	for(int i = 1; i <= N; ++i){
		int L = i - l[i - 1];
		int R = i + r[i] - M;
		if(L <= R){
			++pos[L];
			--pos[R + 1];
		}	
	}

	int ans = 0, ri = 0;
	for(int i = 1; i <= N; ++i){
		pos[i] += pos[i - 1];
	}
	for(int i = 1; i <= N; ++i){
		if(pos[i]) la[i] = i;
		else la[i] = la[i - 1];
	}

	while(ri != N){
		if(la[ri + 1] == 0 || la[ri + 1] + M - 1 == ri) return -1;
		ri = la[ri + 1] + M - 1;
		ans++;
	}
	
	return ans;
}

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