oj.uz

Submission #714071

# Submission time Handle Problem Language Result Execution time Memory
714071 2023-03-23T19:38:57 Z Drew_ Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 340 KB 
#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)
{
	x -= y;
	return x < 0 ? x + m : x;
	// 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -