Submission #882949

#TimeUsernameProblemLanguageResultExecution timeMemory
882949tsumondaiReal Mountains (CCO23_day1problem2)C++14
25 / 25
3619 ms279816 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e6 + 5; const int oo = 1e18, mod = 1e6 + 3; int n, m, k, h[N]; map<int, vector<int>> add, del; set<int> s; int nodes[4*N]; void build(int id, int l, int r) { if (l == r) { nodes[id] = h[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); nodes[id] = min(nodes[id << 1], nodes[id << 1 | 1]); } void update(int id, int l, int r, int pos) { if (l == r) { nodes[id] = oo; return; } int mid = (l + r) >> 1; if (pos <= mid) update(id << 1, l, mid, pos); else update(id << 1 | 1, mid + 1, r, pos); nodes[id] = min(nodes[id << 1], nodes[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if (u > r || v < l /*|| l>r || u>v*/) return oo; if (l >= u && r <= v) return nodes[id]; int mid = (l + r) >> 1; return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } int calc(int l, int r) { if (s.empty()) return 0; int res = 0; int x = *s.begin(), y = *s.rbegin(); int lx = get(1, 1, n, 1, x), ry = get(1, 1, n, y, n); int sum = ((r - l) * (l + r - 1) / 2) % mod; if (x == y) return ((lx + ry) * (r - l) + sum) % mod; int add = lx + ry + r; res = (res + add * (r - l)) % mod; int sz = (int)s.size(); res = ((res + (3 * sum + 2 * (r - l)) * (sz - 1) - (r - l)) % mod + mod) % mod; return res; } void process() { cin >> n; foru(i, 1, n) { cin >> h[i]; add[h[i]].pb(i); } build(1, 1, n); int p = max_element(h + 1, h + n + 1) - h; foru(i, 1, p) h[i] = max(h[i], h[i - 1]); ford(i, n, p) h[i] = max(h[i], h[i + 1]); foru(i, 1, n) del[h[i]].push_back(i); int pre = -1, ans = 0; for (auto &it : add) { if (pre != -1) ans = (ans + calc(pre, it.fi)) % mod; for (int x : it.se) { s.insert(x); update(1, 1, n, x); } for (int x : del[it.fi]) s.erase(x); pre = it.fi; } cout << ans << '\n'; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } /* Xét các trường hợp đặc biệt Kiểm tra lại input/output Cố gắng trâu Lật ngược bài toán Keep calm and get VOI Flow: */
#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...