Submission #292515

#	Time	Username	Problem	Language	Result	Execution time	Memory
292515		amoo_safar	Painting Walls (APIO20_paint)	C++17	100 / 100	507 ms	13688 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int Log = 20;

vector<int> Lov[N];
int R[N], L[N], ps[N];

int minimumInstructions(int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){
	memset(R, 0, sizeof R);
	memset(L, 0, sizeof L);
	memset(ps, 0, sizeof ps);

	for(int i = 0; i < m; i++){
		assert(A[i] == (int) B[i].size());
		for(auto x : B[i]){
			Lov[x].pb(i);
		}
	}
	int col;
	for(int i = 0; i < n; i++){
		col = C[i];
		assert(col < k);
		for(auto &x : Lov[col]){
			if(x <= i && R[i - x] == x) R[i - x] ++;
		}
	}
	for(int i = n - 1; i >= 0; i--){
		col = C[i];
		for(auto &x : Lov[col]){
			if((m - 1 - x) <= n - 1 - i && L[i + (m - 1 - x) + 1] == (m - 1 - x)) L[i + (m - 1 - x) + 1] ++;
		}
	}
	
	/*
	map<pii, int> mp;

	for(int i = 0; i < m; i++){
		assert(A[i] == (int) B[i].size());
		for(auto x : B[i]){
			Lov[x].pb(i);
		}
	}
	*/



	int ls, rs;	
	for(int i = 0; i <= n; i++){
		if(L[i] + R[i] < m) continue;
		ls = i - L[i];
		rs = ls + ((R[i] + L[i]) - m);
		rs = min(rs, n);
		ls = max(ls, 0);

		ps[ls] ++;
		ps[rs + 1] --;
	}
	for(int i = 1; i <= n; i++) ps[i] += ps[i - 1];
	/*
	vector<int> pos;
	for(int i = 0; i < n; i++){
		if(i + m <= n && ps[i] > 0)
			pos.pb(i);
	}
	*/
	int laa = -1, la = 0, ans = 0;
	while(la < n){
		bool flg = false;
		for(int i = la; i > laa; i--){
			if(i + m <= n && ps[i] > 0){
				laa = la;
				la = i + m;
				flg = true;
				break;
			}
		}
		if(flg) ans ++;
		else return -1;
	}
	return ans;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

*/

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