Submission #705225

#	Time	Username	Problem	Language	Result	Execution time	Memory
705225		rainboy	Abracadabra (CEOI22_abracadabra)	C11	100 / 100	673 ms	46172 KiB

Main

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

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define Q	1000000

int min(int a, int b) { return a < b ? a : b; }

int *eh[N + 1], eo[N + 1];

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

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

int st[N_ * 2], n_;

void pul(int i) {
	st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}

void update(int i, int x) {
	st[i += n_] = x;
	while (i > 1)
		pul(i >>= 1);
}

int x, y, z;

void query(int k) {
	int i = 1;

	while (i < n_)
		if (k < st[i << 1 | 0])
			i = i << 1 | 0;
		else
			k -= st[i << 1 | 0], i = i << 1 | 1;
	x = i - n_, y = k, z = st[i];
}

int main() {
	static int aa[N], ii[N], nxt[N], qu[N], ii_[Q], ans[Q];
	int n, q, cnt, h, i, j, t, o;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		ii[aa[i]] = i;
	}
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && aa[i] > aa[qu[cnt - 1]])
			cnt--;
		nxt[i] = cnt == 0 ? n : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (t = 0; t <= n; t++)
		eh[t] = (int *) malloc(2 * sizeof *eh[t]);
	for (h = 0; h < q; h++) {
		scanf("%d%d", &t, &ii_[h]), ii_[h]--, t = min(t, n);
		append(t, h);
	}
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	i = 0;
	while (i < n)
		update(aa[i], nxt[i] - i), i = nxt[i];
	for (t = 0; t <= n; t++) {
		for (o = eo[t]; o--; ) {
			h = eh[t][o];
			query(ii_[h]);
			ans[h] = aa[ii[x] + y] + 1;
		}
		query(n / 2);
		i = ii[x];
		update(x, y);
		for (j = i + y; j < i + z; j = nxt[j])
			update(aa[j], min(nxt[j], i + z) - j);
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25