Submission #488550

#	Time	Username	Problem	Language	Result	Execution time	Memory
488550		rainboy	Volontiranje (COCI21_volontiranje)	C11	110 / 110	278 ms	66948 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define N	1000000

int max(int a, int b) { return a > b ? a : b; }

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int *ei[N], eo[N];

void append(int h, int i) {
	int o = eo[h]++;

	if (o >= 2 && (o & o - 1) == 0)
		ei[h] = (int *) realloc(ei[h], o * 2 * sizeof *ei[h]);
	ei[h][o] = i;
}

int main() {
	static int aa[N], nxt[N], hh[N];
	int n, h, i, j, l, c;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	for (i = 0; i < n; i++)
		update(aa[i], n, (hh[i] = query(aa[i])) + 1);
	l = query(n - 1);
	for (h = 0; h < l; h++)
		ei[h] = (int *) malloc(2 * sizeof *ei[h]);
	for (i = 0; i < n; i++) {
		append(hh[i], i);
		nxt[i] = -1;
	}
	c = 0, h = 0;
	while (1)
		if (h == l) {
			for (h = 0; h < l; h++)
				nxt[ei[h][eo[h] - 1]] = h + 1 == l ? n : ei[h + 1][eo[h + 1] - 1], eo[h]--;
			c++, h = 0;
		} else {
			if (eo[h] == 0)
				break;
			if (h > 0) {
				if (ei[h - 1][eo[h - 1] - 1] > ei[h][eo[h] - 1]) {
					eo[--h]--;
					continue;
				}
				if (aa[ei[h - 1][eo[h - 1] - 1]] > aa[ei[h][eo[h] - 1]]) {
					eo[h]--;
					continue;
				}
			}
			h++;
		}
	printf("%d %d\n", c, l);
	for (i = 0; i < n; i++)
		if (hh[i] == 0 && nxt[i] != -1) {
			for (j = i; j < n; j = nxt[j])
				printf("%d ", j + 1);
			printf("\n");
		}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:32:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   32 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60