Submission #1287822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287822		AbdullahIshfaq	Real Mountains (CCO23_day1problem2)	C++20	0 / 25	1 ms	572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000003
const int N = 1000005;
ll n, h[N], pref[N], suff[N], tar[N];
vector<int> ord;
int sm(int l, int r)
{
	return (l + r) * (r - l + 1) / 2 % MOD;
}
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> h[i];
		ord.push_back(h[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		pref[i] = max(pref[i - 1], h[i]);
	}
	for (int i = n; i >= 1; i--)
	{
		suff[i] = max(suff[i + 1], h[i]);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		tar[i] = min(pref[i], suff[i]);
		ans = (ans + sm(h[i], tar[i] - 1)) % MOD;
	}
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	ll last = 0;
	for (int j : ord)
	{
		ll ok = 0, mn = 1e10, cnt = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (tar[i] >= j and h[i] < j)
			{
				if (!ok)
				{
					ans = (ans + (mn * (j - last)) % MOD) % MOD;
				}
				ok = 1;
				cnt++;
			}
			if (h[i] >= j)
			{
				mn = min(mn, h[i]);
			}
		}
		ok = 0, mn = 1e10;
		for (int i = n; i >= 1; i--)
		{
			if (tar[i] >= j and h[i] < j)
			{
				if (!ok)
				{
					ans = (ans + (mn * (j - last)) % MOD) % MOD;
				}
				else
				{
					ans = (ans + sm(last + 1, j)) % MOD;
				}
				ok = 1;
			}
			if (h[i] >= j)
			{
				mn = min(mn, h[i]);
			}
		}
		if (cnt == 2)
		{
			ans = (ans + (mn * (j - last))) % MOD;
		}
		last = j;
	}
	cout << ans << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++)
	{
		solve();
	}
}

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