Submission #1206914

#TimeUsernameProblemLanguageResultExecution timeMemory
1206914thangdzwinioiReal Mountains (CCO23_day1problem2)C++20
25 / 25
1018 ms164736 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 1e6 + 5; const int mod = 1e6 + 3; int n, h[MAX], pref[MAX], suff[MAX], tar[MAX]; vector <int> ord; int fd(int value){ return lower_bound(ord.begin(), ord.end(), value) - ord.begin(); } int sr(int l, int r){ return 1ll * (l + r) * (r - l + 1) / 2 % mod; } int mul(int a, int b){ return 1ll * a * b % mod; } void add(int &a, int b){ a += b; if (a >= mod) a -= mod; } int cnt[MAX], siz; pair <int, int> st[MAX << 2]; pair <int, int> inf = {1e9, 0}; pair <int, int> operator + (const pair <int, int> &A, const pair <int, int> &B){ return make_pair(min(A.first, B.first), max(A.second, B.second)); } void update(int u, int v, int val, int s = 1, int l = 1, int r = siz - 1){ if (u <= l && r <= v){ st[s] = st[s] + make_pair(val, val); return; } int mid = l + r >> 1; if (mid >= u) update(u, v, val, s << 1, l, mid); if (mid < v) update(u, v, val, s << 1 | 1, mid + 1, r); } pair <int, int> cur[MAX]; void dfs(int s = 1, int l = 1, int r = siz - 1){ if (l == r) { cur[l] = st[s]; return; } int mid = l + r >> 1; for (int child : {s << 1, s << 1 | 1}) st[child] = st[child] + st[s]; dfs(s << 1, l, mid); dfs(s << 1 | 1, mid + 1, r); } vector <int> pos[MAX]; void process(){ cin >> n; for (int i = 1; i <= n; ++ i) { cin >> h[i]; ord.push_back(h[i]); } sort(ord.begin(), ord.end()); ord.erase(unique(ord.begin(), ord.end()), ord.end()); siz = ord.size(); if (siz == 1){ cout << 0; return; } 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]); for (int i = 1; i <= siz * 4; ++ i) st[i] = inf; int ans = 0; for (int i = 1; i <= n; ++ i){ tar[i] = min(pref[i], suff[i]); add(ans, sr(h[i], tar[i] - 1)); int l = fd(h[i]) + 1, r = fd(tar[i]) + 1; pos[l - 1].push_back(i); if (l < r){ cnt[l] ++, cnt[r] --; update(l, r - 1, i); } } dfs(); for (int i = 1; i < siz; ++ i) cnt[i] += cnt[i - 1]; set <int> sf, pf; for (int i = siz - 1; i > 0; -- i){ for (int p : pos[i]){ pf.insert(p); auto curp = pf.upper_bound(p); while (curp != pf.end()) curp = pf.erase(curp); sf.insert(p); auto curf = sf.lower_bound(p); while (curf != sf.begin()){ curf --; curf = sf.erase(curf); } } int dist = ord[i] - ord[i - 1]; int cost = sr(ord[i - 1] + 1, ord[i]); if (cnt[i] == 0) continue; int l = *(--pf.upper_bound(cur[i].first)); int r = *(sf.lower_bound(cur[i].second)); add(ans, mul(h[l] + h[r], dist)); if (cnt[i] == 1) continue; if (cnt[i] >= 2){ add(ans, mul(cnt[i] * 2 - 3, cost)); add(ans, mul(h[*sf.begin()], dist)); } } cout << ans; } int main(){ //freopen("chill.inp", "r", stdin); //freopen("chill.ans", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); process(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...