Submission #1150835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150835		pinbu	Painting Walls (APIO20_paint)	C++20	100 / 100	1449 ms	506392 KiB

paint

#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 100005;

vector<int> arr1[MXn], arr2[MXn], nxt[MXn];
int prf[MXn];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    for (int i = 0; i < M; i++) {
    	for (int c: B[i]) arr1[c].emplace_back(i);
    }
    for (int i = 0; i < N; i++) {
    	arr2[i] = arr1[C[i]];
    	nxt[i].resize(sz(arr2[i]));
    }
    for (int j = 0; j < sz(nxt[N - 1]); j++) nxt[N - 1][j] = N - 1;
    for (int i = N - 2; i >= 0; i--) {
    	for (int j = 0; j < sz(nxt[i]); j++) {
    		nxt[i][j] = i;
    		int p = lower_bound(begin(arr2[i + 1]), end(arr2[i + 1]), (arr2[i][j] + 1) % M) - arr2[i + 1].begin();
    		if (p < sz(arr2[i + 1]) && arr2[i + 1][p] == ((arr2[i][j] + 1) % M)) {
    			nxt[i][j] = min(i + M - 1, nxt[i + 1][p]);
    		}
    	}
    }
    for (int i = 0; i <= N - M; i++) {
    	int able = 0;
    	for (int j = 0; j < sz(nxt[i]); j++) {
    		if (nxt[i][j] == i + M - 1) {
    			able = 1;
    			break;
    		}
    	}
    	prf[i] = able;
    	if (i > 0) prf[i] += prf[i - 1];
    }
    
    int ans = -1;
    if (prf[0]) {
    	int tmp = 1;
    	int cur = 0;
	    while (cur < N - M) {
	    	int l = cur + 1, r = min(cur + M, N - M), mid, pos;
	    	int num = prf[r] - prf[l - 1];
	    	if (!num) tmp = -N;
	    	while (l <= r) {
	    		mid = (l + r) >> 1;
	    		if (prf[mid] - prf[cur] == num) {
	    			pos = mid;
	    			r = mid - 1;
	    		} else l = mid + 1;
	    	}
	    	tmp++;
	    	cur = pos;
	    }
	    ans = max(ans, tmp);
    }
	
	return ans;
}

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