Submission #387312

#	Time	Username	Problem	Language	Result	Execution time	Memory
387312		milleniumEeee	Painting Walls (APIO20_paint)	C++17	63 / 100	1581 ms	161100 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
//#include "grader.cpp"
#define all(s) s.begin(), s.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
 
const int MAXN = (int)1e5 + 5;
const int INF = 1e9 + 7;
 
int pos[MAXN];
int dp[MAXN];
int pref[MAXN];
 
struct Segment_Tree {
	vector <int> tree;
	vector <int> lazy;
	Segment_Tree (int n) {
		tree.resize(n * 4, INF);
		lazy.resize(n * 4, INF);
	}
	void push(int v, int tl, int tr) {
		if (lazy[v] == INF) {
			return;
		}
		if (tl != tr) {
			chkmin(lazy[v + v], lazy[v]);
			chkmin(lazy[v + v + 1], lazy[v]);
		}
		chkmin(tree[v], lazy[v]);
		lazy[v] = INF;
	}
	void upd(int l, int r, int val, int v, int tl, int tr) {
		push(v, tl, tr);
		if (l > tr || tl > r) {
			return;
		}
		if (l <= tl && tr <= r) {
			lazy[v] = val;
			push(v, tl, tr);
			return;
		}
		int mid = (tl + tr) >> 1;
		upd(l, r, val, v + v, tl, mid);
		upd(l, r, val, v + v + 1, mid + 1, tr);
		tree[v] = min(tree[v + v], tree[v + v + 1]);
	}
	int get(int l, int r, int v, int tl, int tr) {
		push(v, tl, tr);
		if (l > tr || tl > r) {
			return INF;
		}
		if (l <= tl && tr <= r) {
			return tree[v];
		}
		int mid = (tl + tr) >> 1;
		return min(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
	}
};
 
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	memset(pos, -1, sizeof(pos));
	bool subtask1 = true;
	for (int i = 0; i < M; i++) {
		for (int el : B[i]) {
			if (pos[el] != -1) {
				subtask1 = false;
			}
			pos[el] = i;
		}
	}
	for (int i = 0; i < N; i++) {
		if (pos[C[i]] == -1) {
			return -1;
		}
	}
	auto nxt = [&](int p) {
		if (p + 1 < M) {
			return p + 1;
		} else {
			return 0;
		}
	};
	for (int i = 0; i + 1 < N; i++) {
		int before = (i > 0 ? pref[i - 1] : 0);
		pref[i] = before + (pos[C[i + 1]] == nxt(pos[C[i]]));
	}
	auto get = [&](int l, int r) {
		return pref[r - 1] - pref[l - 1];
	};
	
	
	bool subtask3 = (N <= 20000 && M <= min(N, 2000));
	//subtask3 = false; // wtf
	vector <vector<int>> Q;
	vector <int> MAXQ;
	if (subtask3) {
		Q.resize(N + 1);
		MAXQ.resize(N + 1);
		for (auto &el : Q) {
			el.resize(M, 0);
		}
		auto exist = [&](vector <int> &vec, int color) {
			return binary_search(all(vec), color);
		};
		
		for (int i = N - 1; i >= 0; i--) {
			MAXQ[i] = 0;
			for (int j = 0; j < M; j++) {
				if (exist(B[j], C[i])) {
					int add = 0;
					if (i + 1 < N) {
						add = Q[i + 1][(j + 1) % M];
					}
					Q[i][j] = 1 + add;
				} else {
					Q[i][j] = 0;
				}
				MAXQ[i] = max(MAXQ[i], Q[i][j]);
			}
		}
	}
	auto can = [&](int l, int r) {
		if (subtask3) {
			return l + MAXQ[l] - 1 >= r;
		}
		if (subtask1) {
			if (r - l + 1 == M && get(l, r) == M - 1) {
				return true;
			} else {
				return false;
			}			
		} else {
			for (int x = 0; x < M; x++) {
				bool ok = 1;
				int step = 0;
				int pos = x;
				while (1) {
					ok &= (binary_search(all(B[pos]), C[l + step]));
					step++;
					pos = nxt(pos);
					if (step == M) {
						break;
					}
				}
				if (ok) {
					return true;
				}
			}
			return false;
		}
	};
	fill(dp, dp + MAXN, INF);
	Segment_Tree T(N);
	if (can(0, M - 1)) {
		T.upd(0, M - 1, 1, 1, 0, N - 1);
	}
	for (int i = M; i < N; i++) {
		if (can(i - M + 1, i)) {
			int best = T.get(i - M, i - 1, 1, 0, N - 1);
			T.upd(i - M + 1, i, best + 1, 1, 0, N - 1);
		}
	}
	if (T.get(N - 1, N - 1, 1, 0, N - 1) < INF) {
		return T.get(N - 1, N - 1, 1, 0, N - 1);
	} else {
		return -1;
	}
}
 
/*
5 3 10
0 2 1 4 3
2 0 4
2 3 2
1 1
*/

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:90:34: warning: array subscript -1 is below array bounds of 'int [100005]' [-Warray-bounds]
   90 |   return pref[r - 1] - pref[l - 1];
      |                        ~~~~~~~~~~^

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