Submission #823240

#	Time	Username	Problem	Language	Result	Execution time	Memory
823240		rainboy	Real Mountains (CCO23_day1problem2)	C11	25 / 25	294 ms	29436 KiB

Main

#include <stdio.h>

#define N	1000000
#define INF	0x3f3f3f3f
#define MD	1000003

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N + 2];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int main() {
	static int ii[N], pp[N + 2], qq[N + 2], bb[N + 2];
	int n, h, i, p, q, al, ar, ak, as, l, r, k, ans;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &aa[i]);
		ii[i - 1] = i;
	}
	sort(ii, 0, n);
	for (i = 0; i <= n + 1; i++)
		pp[i] = i - 1, qq[i] = i + 1;
	ans = 0;
	for (h = n - 1, l = n + 2, r = -1; h > 0; h--) {
		i = ii[h];
		l = min(l, i), r = max(r, i);
		p = pp[i], q = qq[i];
		qq[p] = q, pp[q] = p, bb[p] = aa[i];
		k = r - l + 1 - (n - h);
		if (k == 0)
			continue;
		al = aa[ii[h - 1]], ar = aa[ii[h]];
		ak = ar - al, as = (long long) ak * (al + ar - 1) / 2 % MD;
		ans = (ans + ((long long) as * 3 + ak * 2) * k) % MD;
		if (k == 1)
			ans = (ans + ((long long) bb[l - 1] + bb[pp[r + 1]]) * ak - (long long) (as + ak) * 2) % MD;
		else
			ans = (ans + ((long long) bb[l - 1] + bb[pp[r + 1]] + aa[ii[h]]) * ak - (long long) (as + ak) * 3) % MD;
	}
	if (ans < 0)
		ans += MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

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