Submission #773227

#	Time	Username	Problem	Language	Result	Execution time	Memory
773227		rainboy	Rainy Markets (CCO22_day1problem2)	C11	25 / 25	1085 ms	105556 KiB

Main

#include <stdio.h>

#define N	1000000
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(N))) */

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

long long ss[N_ * 2], qq[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	ss[i] = ss[l] + ss[r];
	qq[i] = min(qq[l] + ss[r], qq[r]);
}

void update(int i, long long x) {
	i += n_;
	ss[i] += x, qq[i] = min(ss[i], 0);
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int aa[N], bb[N], cc[N], dd[N], qu[N];
	int n, cnt, i, j, a, b, d;
	long long c, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i + 1 < n; i++)
		scanf("%d", &bb[i]);
	for (i = 0; i + 1 < n; i++) {
		scanf("%d", &cc[i]);
		cc[i] = min(cc[i], bb[i]);
	}
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	cnt = 0, ans = 0;
	for (j = 0; j + 1 < n; j++) {
		update(j, aa[j] - bb[j]);
		if (cc[j] > 0)
			qu[cnt++] = j;
		c = -min(qq[1] + aa[j + 1], 0);
		ans += c;
		while (c > 0 && cnt) {
			i = qu[cnt - 1];
			d = min(c, cc[i]);
			update(i, d);
			c -= d, bb[i] -= d, cc[i] -= d, dd[i] += d;
			if (cc[i] == 0)
				cnt--;
		}
		if (qq[1] + aa[j + 1] < 0) {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	printf("%lld\n", ans);
	for (i = 0; i + 1 < n; i++) {
		a = min(bb[i], aa[i]), d = dd[i], b = bb[i] - a;
		printf("%d %d %d\n", a, d, b);
		aa[i + 1] -= b;
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:29:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:31:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:33:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d", &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:35:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9