Submission #770119

#	Time	Username	Problem	Language	Result	Execution time	Memory
770119		rainboy	Bigger segments (IZhO19_segments)	C11	100 / 100	50 ms	16780 KiB

segments

#include <stdio.h>

#define N	500000

int main() {
	static long long aa[N + 1], bb[N + 1];
	static int pp[N + 1], qu[N + 1];
	int n, cnt, h, i;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &aa[i]);
		aa[i] += aa[i - 1];
	}
	pp[0] = 0, bb[0] = 0;
	cnt = 0;
	qu[cnt++] = 0;
	for (h = 0, i = 1; i <= n; i++) {
		while (h + 1 < cnt && bb[qu[h + 1]] <= aa[i])
			h++;
		pp[i] = qu[h], bb[i] = aa[i] * 2 - aa[pp[i]];
		while (cnt && bb[qu[cnt - 1]] >= bb[i])
			cnt--;
		qu[cnt++] = i;
	}
	i = n, cnt = 0;
	while (i > 0)
		i = pp[i], cnt++;
	printf("%d\n", cnt);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27