Submission #1000647

#TimeUsernameProblemLanguageResultExecution timeMemory
1000647vjudge1Safety (NOI18_safety)C++17
100 / 100
168 ms22988 KiB
#include <bits/stdc++.h> #define ll long long #define lb lower_bound #define pii pair<int,int> #define pll pair<ll,ll> #define F first #define S second #define ld long double #define pb push_back #define all(v) v.begin(),v.end() #define in insert #define sz(s) (int)s.size() #define int ll using namespace std; const int MAX=2e5+10; const int inf=2e9; int n,H; int a[MAX]; void solve(){ cin>>n>>H; multiset<int> l,r; for(int i=1;i<=n;i++){ cin>>a[i]; } int st=0; int slope=0; int add=0; for(int i=1;i<=n;i++){ add+=H; st+=a[i]+add; slope--; l.in(a[i]+add); l.in(a[i]+add); while(!r.empty()&&!l.empty()&&*l.rbegin()-2*add>*r.begin()){ int L=*r.begin()+2*add; int R=*l.rbegin()-2*add; l.erase(--l.end()); r.erase(r.begin()); l.in(L); r.in(R); } while(sz(l)>abs(slope)){ r.in(*l.rbegin()-2*add); l.erase(--l.end()); } } vector<int> vec; for(int x:l){ // cout<<x-add<<" "; vec.pb(x-add); } // cout<<"\n"; // cout<<st<<" "<<*r.rbeg<<"\n"; int prev=-add; for(int i=0;i<sz(vec);i++){ st+=(vec[i]-prev)*slope; prev=vec[i]; slope++; } cout<<st<<"\n"; } // #ifdef LOCAL signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--)solve(); } // #endif
#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...