Submission #1162730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162730		Pwo	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	1437 ms	96576 KiB

Main

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

int modMul(int a, int b) {
    return ((a % md) * (b % md)) % md;
}

int modAdd(int a, int b) {
    return ((a % md) + (b % md)) % md;
}

int n, a[1000005], b[1000005];
vector<pair<int, int>> v;
set<int> st;
int t[2048576];

void update(int p, int v) {
	for (t[p += n] = v; p > 1; p >>= 1) t[p >> 1] = min(t[p], t[p ^ 1]);
}
	
int query(int l, int r) {
	int res = 1e18;
	for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res = min(res, t[l++]);
		if (r & 1) res = min(res, t[--r]);
	}
	return res;
}
 
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, 1e18);
	fill(t, t + 2048576, 1e18);
	
	int ans = 0, prev = c;
	int lo = 1e18, hi = -1, inv2 = 500002;
	while (j < n) {
		vector<int> idx;
		while (v[j].first == c) {
			idx.push_back(v[j].second);
			j++;
		}
		
		if (!st.empty()) {
			int fi = *st.begin(), la = *st.rbegin();
            int diff = (prev - c) % md;
            if (st.size() == 1) {
                int cont = (query(1, fi) + query(fi, n)) % md;
                ans = (ans + modMul(cont, diff)) % md;
                int temp = modMul(modMul((c + prev - 1) % md, diff), inv2);
                ans = (ans + temp) % md;
            } else {
                int cont = (query(1, fi) + query(la, n) + 2 * (int) st.size() - 3) % md;
                int t1 = query(fi, n), t2 = query(1, la);
                if (t1 < t2) cont = (cont + t1) % md;
                else cont = (cont + t2) % md;
                ans = (ans + modMul(cont, diff)) % md;
                
                int f = (3 * (int) st.size() - 3) % md;
                int temp = modMul(modMul(modMul((c + prev - 1) % md, diff), inv2), f);
                ans = (ans + temp) % md;
            }
		}
		
		int nlo = lo, nhi = hi;
		for (const int u : idx) {
			b[u] = c;
			update(u, c);
			st.erase(u);
			nlo = min(u, nlo);
			nhi = max(u, nhi);
		}
		if (hi != -1) {
			for (int i = hi + 1; i < nhi; i++) if (b[i] == 1e18) st.insert(i);
			for (int i = nlo + 1; i < lo; i++) if (b[i] == 1e18) st.insert(i);
		} else {
			for (int i = nlo + 1; i < nhi; i++) if (b[i] == 1e18) st.insert(i);
		}
		lo = nlo, hi = nhi;
		
		if (j >= n) break;
		prev = c;
		c = v[j].first;
	}
	
	cout << ans;
}

• 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