Submission #708017

#	Time	Username	Problem	Language	Result	Execution time	Memory
708017		rainboy	Snowball (JOI21_ho_t2)	C11	100 / 100	117 ms	13716 KiB

Main

#include <stdio.h>

#define N	200000
#define Q	200000

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

int main() {
	static long long xx[N], aa[Q + 1], bb[Q + 1], ans[N];
	int n, q, h, i, lower, upper;
	long long d, x;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%lld", &xx[i]);
	x = 0;
	for (h = 0; h < q; h++) {
		scanf("%lld", &d);
		x += d;
		aa[h + 1] = max(aa[h], -x), bb[h + 1] = max(bb[h], x);
	}
	ans[0] += aa[q], ans[n - 1] += bb[q];
	for (i = 1; i < n; i++) {
		x = xx[i] - xx[i - 1];
		lower = -1, upper = q + 1;
		while (upper - lower > 1) {
			h = (lower + upper) / 2;
			if (aa[h] + bb[h] <= x)
				lower = h;
			else
				upper = h;
		}
		h = lower;
		if (h == q)
			ans[i - 1] += bb[h], ans[i] += aa[h];
		else if (aa[h] < aa[h + 1])
			ans[i - 1] += bb[h], ans[i] += x - bb[h];
		else
			ans[i - 1] += x - aa[h], ans[i] += aa[h];
	}
	for (i = 0; i < n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%lld", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%lld", &d);
      |   ^~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67