Submission #968558

#TimeUsernameProblemLanguageResultExecution timeMemory
968558weakweakweakReal Mountains (CCO23_day1problem2)C++17
25 / 25
2740 ms129472 KiB
//我好笨,聽解了 /* x + */ #include <bits/stdc++.h> using namespace std; using ll = long long; const int M = 1e6 + 3, N = M + 20, INF = (INT_MAX >> 1) - 3; int o[N], n; vector <int> v[N], b; struct segmenttree { int a[N << 2]; void build (int l, int r, int id) { if (l == r) { a[id] = b[o[l]]; return; } int mid = (l + r) >> 1; build (l, mid, id << 1); build (mid + 1, r, id << 1 | 1); a[id] = min(a[id << 1], a[id << 1 | 1]); } int query (int l, int r, int ql, int qr, int id) { if (ql < 1 or qr > n or ql > qr) return INF; if (ql <= l and r <= qr) return a[id]; int mid = (l + r) >> 1, ans = INT_MAX; if (ql <= mid) ans = min(ans, query(l, mid, ql, qr, id << 1)); if (qr > mid) ans = min(ans, query(mid + 1, r, ql, qr, id << 1 | 1)); return ans; } void update (int l, int r, int pos, int val, int id) { if (l == r) { a[id] = o[pos] = val; return; } int mid = (l + r) >> 1; if (pos <= mid) update(l, mid, pos, val, id << 1); else update(mid + 1, r, pos, val, id << 1 | 1); a[id] = min(a[id << 1], a[id << 1 | 1]); } }seg; inline int f (int l, int r) { return (r - l + 1LL) * (r + l) / 2 % M; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> o[i]; b.push_back(o[i]); } sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); for (int i = 1; i <= n; i++) { o[i] = lower_bound(b.begin(), b.end(), o[i]) - b.begin(); v[o[i]].push_back(i); } seg.build(1, n, 1); set<int> st; ll ans = 0; for (int h = 0; h + 1 < b.size(); h++) { int oh = b[h], nh = b[h + 1]; for (int x : v[h]) { st.insert(x); seg.update(1, n, x, INF, 1); } while (st.size()) { int i = *st.begin(); int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1); if (left == INF or right == INF) st.erase(i); else break; } while (st.size()) { int i = *st.rbegin(); int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1); if (left == INF or right == INF) st.erase(i); else break; } if (st.size() == 1) { int i = *st.begin(); int left = seg.query(1, n, 1, i - 1, 1), right = seg.query(1, n, i + 1, n, 1); ans += f(oh, nh - 1) + (left +right) * 1LL * (nh - oh) % M; } else if (st.size() >= 2) { int il = *st.begin(), ir = *st.rbegin(); ll left = seg.query(1, n, 1, il - 1, 1), right = seg.query(1, n, ir + 1, n, 1); ll mid = seg.query(1, n, il + 1, ir - 1, 1); ll z = min( (left + right + min(left, right)) * 1LL * (nh - oh) + f(oh + 1, nh) + f(oh, nh - 1) * 2 , (left + mid + right) * 1LL * (nh - oh) + f(oh + 1, nh) + f(oh, nh - 1) * 2 ); ans += z % M; ans += (st.size() - 2) * (f(oh + 1, nh) * 2LL + f(oh, nh - 1)) % M; } ans %= M; } cout << ans << '\n'; return 0;}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int h = 0; h + 1 < b.size(); h++) {
      |                     ~~~~~~^~~~~~~~~~
#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...