Submission #714070

#	Time	Username	Problem	Language	Result	Execution time	Memory
714070		Drew_	Painting Walls (APIO20_paint)	C++17	63 / 100	1547 ms	14484 KiB

paint

#include "paint.h"

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

#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second

int const MAX = 1e5 + 7;

inline int add(int x, int y, int m)
{
	return (x + y) % m;
}

inline int sub(int x, int y, int m)
{
	return ((x - y) % m + m) % m;
}

vector<int> ctr;
vector<int> fq;

vector<vector<int>> painter;
inline void insert(int color, int pos, int M)
{
	for (int x : painter[color])
	{
		fq[ctr[sub(pos, x, M)]]--;
		fq[++ctr[sub(pos, x, M)]]++;
		//update(sub(pos, x, M), 1);
	}
}

inline void remove(int color, int pos, int M)
{
	for (int x : painter[color])
	{
		fq[ctr[sub(pos, x, M)]]--;
		fq[--ctr[sub(pos, x, M)]]++;
		//update(sub(pos, x, M), -1);
	}
}

int minimumInstructions(
	int N, int M, int K, std::vector<int> C,
	std::vector<int> A, std::vector<std::vector<int>> B) 
{	
	ctr.resize(M+1);
	fq.resize(M+1);

	painter.resize(K);
	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < A[i]; ++j)
			painter[B[i][j]].pb(i);
	}

	for (int i = 0; i < M-1; ++i)
		insert(C[i], i, M);

	//for (int i = 0; i < M; ++i)
	//	cout << ctr[i] << " ";

	queue<ii> q;
	for (int i = M-1; i < N; ++i)
	{
		insert(C[i], i, M);

		//if (rmaxq(0, M) == M)
		if (fq[M])
		{
			if (i == M-1)
			{
				q.push({i, 1});

				if (i == N-1)
					return 1;
			}
			else
			{
				while (!q.empty() && q.front().f1 < i - M)
					q.pop();

				if (q.empty())
					return -1;

				if (i == N-1)
					return q.front().s2 + 1;

				q.push({i, q.front().s2 + 1});
			}
		}

		remove(C[i-M+1], i-M+1, M);
	}

	return -1;
}

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