Submission #993597

#	Time	Username	Problem	Language	Result	Execution time	Memory
993597		Trisanu_Das	Real Mountains (CCO23_day1problem2)	C++17	25 / 25	398 ms	29632 KiB

Main

#include <bits/stdc++.h>
#define N	1000000
#define MD	1000003
using namespace std;
 
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;
	cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> 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;
	cout << ans << '\n';
}

• 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