Submission #680342

#	Time	Username	Problem	Language	Result	Execution time	Memory
680342		rainboy	Candies (JOI18_candies)	C11	100 / 100	108 ms	8416 KiB

candies

#include <stdio.h>

#define N	200000

int ll[N], rr[N]; long long aa[N];
int iq[N + 1], pq[N], cnt;

int lt(int i, int j) { return aa[i] > aa[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

void pq_remove(int i) {
	int j = iq[cnt--];

	if (j != i)
		pq[j] = pq[i], pq_up(j), pq_dn(j);
	pq[i] = 0;
}

int main() {
	int n, k, i, l, r;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%lld", &aa[i]);
	for (i = 0; i < n; i++)
		ll[i] = i, rr[i] = i;
	for (i = 0; i < n; i++)
		pq_add(i);
	ans = 0;
	for (k = 1; k * 2 - 1 <= n; k++) {
		i = pq_remove_first(), l = i == 0 ? -1 : ll[i - 1], r = rr[i] + 1 == n ? n : rr[rr[i] + 1];
		printf("%lld\n", ans += aa[i]);
		if (l >= 0)
			pq_remove(l);
		if (r < n)
			pq_remove(ll[r]);
		if (l >= 0 && r < n)
			aa[l] = aa[l] - aa[i] + aa[ll[r]], pq_add(l);
		if (l >= 0)
			rr[l] = r;
		if (r < n)
			ll[r] = l;
	}
	return 0;
}

Compilation message (stderr)

candies.c: In function 'main':
candies.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
candies.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92