Submission #1162718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162718		Pwo	Real Mountains (CCO23_day1problem2)	C++20	6 / 25	171 ms	844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int md = 1e6 + 3;

int n, a[5005], b[5005], pre[5005], suf[5005];
vector<pair<int, int>> v;
 
int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n; for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) v.emplace_back(a[i], i);
	sort(v.begin(), v.end(), greater<pair<int, int>>());
	int j = 0, c = v[0].first;
	fill(b, b + n + 1, 2e9);
	
	int ans = 0, prev = c;
	pre[0] = 2e9; suf[n + 1] = 2e9;
	int lo = 2e9, hi = 0;
	while (j < n) {
		vector<int> idx;
		while (v[j].first == c) {
			idx.push_back(v[j].second);
			j++;
		}
		
		vector<int> bad;
		for (int i = lo + 1; i < hi; i++) if (b[i] == 2e9)
			bad.push_back(i);
		
		if (!bad.empty()) {
			for (int i = 1; i <= n; i++) pre[i] = min(pre[i - 1], b[i]);
			for (int i = n; i >= 1; i--) suf[i] = min(suf[i + 1], b[i]);
			if (bad.size() == 1) {
				int cont = pre[bad[0]] + suf[bad[0]];
				ans += ((cont % md) * (prev - c) % md) % md;
				ans %= md;
				ans += (((c + prev - 1) % md) * ((prev - c) % md) * 500002) % md;
				ans %= md;
			} else {
				int cont = pre[bad[0]] + suf[bad.back()] + 2 * (int) bad.size() - 3;
				if (suf[bad[0]] < pre[bad.back()]) cont += suf[bad[0]];
				else cont += pre[bad.back()];
				ans += cont * (prev - c);
				ans %= md;
				
				int f = (3 * (int) bad.size() - 3) % md;
				ans += f * (((c + prev - 1) % md) * ((prev - c) % md) * 500002) % md;
				ans %= md;
			}
		}
		
		for (const int u : idx) {
			b[u] = c;
			lo = min(u, lo);
			hi = max(u, hi);
		}
		
		if (j >= n) break;
		prev = c;
		c = v[j].first;
	}
	
	cout << ans;
}

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