Submission #364797

#	Time	Username	Problem	Language	Result	Execution time	Memory
364797		abra_stone	Painting Walls (APIO20_paint)	C++14	63 / 100	1315 ms	524292 KiB

paint

#include "paint.h"
#include <vector>
#include <iostream>
#define N 100005
using namespace std;

int ba, sg[N * 4 + 5];
vector<int> ve[N], di[N], dc[N];

void up(int p, int q) {
	p += ba;
	sg[p] = q;
	for (p /= 2; p > 0; p /= 2) {
		sg[p] = min(sg[p * 2], sg[p * 2 + 1]);
	}
}

int get(int p, int q) {
	int re = 1e9;
	p += ba; q += ba;
	while (p < q) {
		if (p % 2 == 1) re = min(re, sg[p]), p++;
		if (q % 2 == 0) re = min(re, sg[q]), q--;
		p /= 2; q /= 2;
	}
	if (p == q) re = min(re, sg[p]);
	return re;
}

int minimumInstructions(int n, int m, int K, vector<int> c, vector<int> a, vector<vector<int> > b) {
	int i, j, k;

	c.push_back(0);
	for (i = c.size() - 1; i > 0; i--) {
		c[i] = c[i - 1];
	}

	for (i = 0; i <= m; i++) {
		di[0].push_back(i);
		dc[0].push_back(0);
	}

	for (i = 0; i < m; i++) {
		for (j = 0; j < a[i]; j++) {
			ve[b[i][j]].push_back(i);
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 0; j < ve[c[i]].size(); j++) {
			di[i].push_back(ve[c[i]][j]);
			dc[i].push_back(0);
		}
		di[i].push_back(1e9);
		dc[i].push_back(-1e9);
		for (j = k = 0; j < di[i].size() - 1; j++) {
			if (di[i][j] == 0) {
				if (di[i - 1][di[i - 1].size() - 2] == m - 1) {
					dc[i][j] = dc[i - 1][di[i - 1].size() - 2] + 1;
				} else {
					dc[i][j] = 1;
				}
			} else {
				for (; di[i - 1][k] < di[i][j] - 1; k++);
				if (di[i - 1][k] == di[i][j] - 1) {
					dc[i][j] = dc[i - 1][k] + 1;
				} else {
					dc[i][j] = 1;
				}
			}
		}
	}
	for (ba = 1; ba < n + 1; ba *= 2);
	for (i = 0; i < ba * 2; i++) sg[i] = 1e9;
	up(0, 0);
	for (i = m; i <= n; i++) {
		for (j = 0; j < dc[i].size() - 1; j++) {
			if (dc[i][j] >= m) {
				int t = get(i - m, i - 1) + 1;
				if (t < sg[ba + i]) up(i, t);
			}
		}
	}
	if (get(n, n) < 1e9) return get(n, n);
	else return -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:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (j = 0; j < ve[c[i]].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~~~
paint.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (j = k = 0; j < di[i].size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
paint.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (j = 0; j < dc[i].size() - 1; j++) {
      |               ~~^~~~~~~~~~~~~~~~~~

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