Submission #1099034

#TimeUsernameProblemLanguageResultExecution timeMemory
1099034noyancanturkSafety (NOI18_safety)C++17
100 / 100
39 ms7036 KiB
#include "bits/stdc++.h" using namespace std; #define int int64_t #define pb push_back using pii=pair<int,int>; const int lim=2e5+100; const int mod=1e9+7; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Local freopen(".in","r",stdin);freopen(".out","w",stdout); #endif int n,h; cin>>n>>h; int a[n]; for(int i=0;i<n;i++)cin>>a[i]; priority_queue<int>p1; priority_queue<int,vector<int>,greater<int>>p2; p1.push(INT_MIN); p2.push(INT_MAX); int ans=0; int shift=0; for(int i=0;i<n;i++){ shift+=h; int leftguy=p1.top()-shift; int rightguy=p2.top()+shift; assert(leftguy<=rightguy); if(leftguy<=a[i]&&a[i]<=rightguy){ p1.push(a[i]+shift); p2.push(a[i]-shift); }else if(rightguy<a[i]){ ans+=a[i]-rightguy; p1.push(rightguy+shift); p2.pop(); p2.push(a[i]-shift); p2.push(a[i]-shift); }else{ ans+=leftguy-a[i]; p2.push(leftguy-shift); p1.pop(); p1.push(a[i]+shift); p1.push(a[i]+shift); } } cout<<ans; }
#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...