Submission #726747

#	Time	Username	Problem	Language	Result	Execution time	Memory
726747		SanguineChameleon	Painting Walls (APIO20_paint)	C++17	100 / 100	469 ms	253896 KiB

paint

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

const int inf = 1e9 + 20;
vector<vector<int>> good;
vector<vector<int>> streak;
vector<int> best_streak;
vector<int> dp;
vector<int> bit;
int N;

void update(int pos, int val) {
	for (int i = pos; i <= N; i += i & (-i)) {
		bit[i] = min(bit[i], val);
	}
}

int get(int pos) {
	int res = inf;
	for (int i = pos; i > 0; i -= i & (-i)) {
		res = min(res, bit[i]);
	}
	return res;
}

int minimumInstructions(int _N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	N = _N;
	bit.resize(N + 1, inf);
	good.resize(K);
	for (int i = 0; i < M; i++) {
		for (auto color: B[i]) {
			good[color].push_back(i);
		}
	}
	streak.resize(N);
	best_streak.resize(N);
	streak[N - 1].resize(good[C[N - 1]].size(), 1);
	for (int i = N - 2; i >= 0; i--) {
		streak[i].resize(good[C[i]].size(), 1);
		int pt = 0;
		for (int j = 0; j < (int)good[C[i]].size(); j++) {
			while (pt < (int)good[C[i + 1]].size() && good[C[i + 1]][pt] < good[C[i]][j] + 1) {
				pt++;
			}
			if (pt < (int)good[C[i + 1]].size() && good[C[i + 1]][pt] == good[C[i]][j] + 1) {
				streak[i][j] = streak[i + 1][pt] + 1; 
			}
			if (good[C[i]][j] == M - 1) {
				if (!good[C[i + 1]].empty() && good[C[i + 1]][0] == 0) {
					streak[i][j] = streak[i + 1][0] + 1; 
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		best_streak[i] = 0;
		for (auto val: streak[i]) {
			best_streak[i] = max(best_streak[i], val);
		}
	}
	dp.resize(N);
	for (int i = N - 1; i >= 0; i--) {
		dp[i] = inf;
		if (best_streak[i] >= M) {
			if (i + M + 1 > N) {
				dp[i] = 1;
			}
			else {
				dp[i] = min(dp[i], get(i + M + 1) + 1);
			}
		}
		update(i + 1, dp[i]);
	}
	if (dp[0] == inf) {
		return -1;
	}
	else {
		return dp[0];
	}
}

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