Submission #1218582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218582		lopkus	Restore Array (RMI19_restore)	C++20	100 / 100	264 ms	680 KiB

restore

#include <stdio.h>

int n, y, m, u[99999], v[99999], w[99999], d[9999];

/* xj - xi <= ww */
void inequality(int i, int j, int ww) {
	u[y] = i;
	v[y] = j;
	w[y] = ww;
	++y;
}

int main() {
	scanf("%d%d", &n, &m);

	for (int l, r, k, value; m--; ) {
		scanf("%d%d%d%d", &l, &r, &k, &value);

		k = (r - l + 2) - k;
		++r;

		if (value) {
			inequality(r, l, -k);
		} else {
			inequality(l, r, k - 1);
		}
	}

	for (int i = 0; i <= n; ++i) {
		if (i) {
			inequality(i - 1, i, 1);
			inequality(i, i - 1, 0);
		}
		d[i] = 1e9;
	}
	d[0] = 0;

	for (int j = 0; j <= n + 1; ++j)
		for (int i = 0; i < y; ++i) {
			if (d[u[i]] + w[i] < d[v[i]]) {
				d[v[i]] = d[u[i]] + w[i];
			}
		}

	for (int i = 0; i < y; ++i) {
		if (d[u[i]] + w[i] < d[v[i]]) {
			puts("-1");
			return 0;
		}
	}

	for (int i = 1; i <= n; ++i)
		printf("%d ", d[i] - d[i - 1]);

	return 0;
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
restore.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 scanf("%d%d%d%d", &l, &r, &k, &value);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55