Submission #1079782

#TimeUsernameProblemLanguageResultExecution timeMemory
107978212345678Safety (NOI18_safety)C++17
100 / 100
64 ms7100 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int nx=2e5+5; ll n, d, h[nx], lzl, lzr, res; priority_queue<ll> pql, pqtl; priority_queue<ll, vector<ll>, greater<ll>> pqr, pqtr; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>d; for (int i=1; i<=n; i++) cin>>h[i]; pql.push(h[1]); pqr.push(h[1]); for (int i=2; i<=n; i++) { lzl-=d; lzr+=d; if (h[i]<pql.top()+lzl) res+=pql.top()+lzl-h[i]; if (h[i]>pqr.top()+lzr) res+=h[i]-pqr.top()-lzr; pql.push(h[i]-lzl); pql.push(h[i]-lzl); while (pql.top()+lzl>pqr.top()+lzr) pqr.push(pql.top()+lzl-lzr), pql.pop(); while (pql.size()>pqr.size()) pqr.push(pql.top()+lzl-lzr), pql.pop(); while (pqr.size()>pql.size()) pql.push(pqr.top()+lzr-lzl), pqr.pop(); } cout<<res; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...