Submission #875895

#	Time	Username	Problem	Language	Result	Execution time	Memory
875895		rainboy	Potatoes and fertilizers (LMIO19_bulves)	C11	100 / 100	289 ms	30548 KiB

bulves

#include <stdio.h>

#define N	500000

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

long long xx[(N + 1) * 2]; int iq[2][(N + 1) * 2 + 1], pq[2][(N + 1) * 2], cnt[2], mode;

int lt(int i, int j) {
	return mode == 0 ? xx[i] > xx[j] : xx[i] < xx[j];
}

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

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

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

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

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

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

int pq_first(int mode_) {
	mode = mode_;
	return iq[mode][1];
}

void pq_remove_first(int mode_) {
	int i, j;

	mode = mode_;
	i = iq[mode][1], j = iq[mode][cnt[mode]--];
	if (j != i)
		pq[mode][j] = 1, pq_dn(j);
	pq[mode][i] = 0;
}

int main() {
	int n, i, i_;
	long long xl, xr, x, x_, ans;

	scanf("%d", &n);
	xl = xr = 0, ans = 0;
	xx[0 << 1 | 0] = 0, pq_add(0, 0 << 1 | 0);
	xx[0 << 1 | 1] = 0, pq_add(1, 0 << 1 | 1);
	for (i = 1; i <= n; i++) {
		int a, b;

		scanf("%d%d", &a, &b);
		xl -= b, xr += a - b;
		x_ = min(xr, 0);
		if ((x = xx[i_ = pq_first(0)] + xl) > 0) {
			ans += x, pq_remove_first(0), xx[i_] += xl - xr, pq_add(1, i_);
			xx[i << 1 | 0] = x_ - xl, pq_add(0, i << 1 | 0);
			xx[i << 1 | 1] = x_ - xl, pq_add(0, i << 1 | 1);
		} else if ((x = xx[i_ = pq_first(1)] + xr) < 0) {
			ans += -x, pq_remove_first(1), xx[i_] += xr - xl, pq_add(0, i_);
			xx[i << 1 | 0] = x_ - xr, pq_add(1, i << 1 | 0);
			xx[i << 1 | 1] = x_ - xr, pq_add(1, i << 1 | 1);
		} else {
			xx[i << 1 | 0] = x_ - xl, pq_add(0, i << 1 | 0);
			xx[i << 1 | 1] = x_ - xr, pq_add(1, i << 1 | 1);
		}
	}
	while (cnt[0] && (x = xx[pq_first(0)] + xl) > 0)
		ans += x, pq_remove_first(0);
	while (cnt[1] && (x = xx[pq_first(1)] + xr) < 0)
		ans += -x, pq_remove_first(1);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36