Submission #489264

#TimeUsernameProblemLanguageResultExecution timeMemory
489264SirCovidThe19thMountain Trek Route (IZhO12_route)C++17
0 / 100
507 ms65540 KiB
#include <bits/stdc++.h> using namespace std; const int mx = 1e6 + 5; template<int sz> struct segTree{ int seg[sz * 2 + 5]; void upd(int i, int num){ seg[i += sz] = num; for (i /= 2; i > 0; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]); } int query(int l, int r){ int ans = 0; for (l += sz, r += sz; l <= r; r /= 2, l /= 2){ if (l % 2 == 1) ans = max(ans, seg[l++]); if (r % 2 == 0) ans = max(seg[r--], ans); } return ans; } };segTree<mx> st; int n, k, A[mx], ans; vector<int> range[mx]; stack<int> stk; int main(){ cin >> n >> k; for (int iter = 0; iter <= 1; iter++){ for (int i = 1; i <= n; i++){ if (!iter) cin >> A[i], st.upd(i, A[i]); while (!stk.empty()){ int L = stk.top(); if (!iter){ int mxTop = st.query(L + 1, i - 1); range[i - L - 1].push_back(min(A[L], A[i]) - mxTop); //cout<<L<<" "<<i<<" "<<min(A[L], A[i]) - mxTop<<endl; } else{ int mxTop = max(st.query(1, i - 1), st.query(L + 1, n)); if (mxTop > min(A[L], A[i])) break; range[n - (L - i + 1)].push_back(min(A[L], A[i]) - mxTop); //cout<<i<<" "<<L<<" "<<min(A[L], A[i]) - mxTop<<endl; } if (A[L] > A[i]) break; stk.pop(); } if (!iter) stk.push(i); } } for (long long len = 1; len <= n; len++){ for (int lim : range[len]){ if (len * lim >= k) ans += 2 * (k / len), k = 0; else ans += 2 * lim, k -= len * lim; } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...