This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+10;
ll n, h, a[N];
priority_queue<ll> l;
priority_queue<ll, vector<ll>, greater<ll>> r;
int main() {
FAST_IO;
cin >> n >> h;
FOR(i, 0, n) cin >> a[i];
l.push(a[0]); r.push(a[0]);
ll add=h, ans=0;
FOR(i, 1, n) {
if(a[i]>r.top()+add) {
ll tp=r.top(); r.pop();
tp+=add;
ans+=a[i]-tp;
tp+=add;
l.push(tp);
r.push(a[i]-add);
r.push(a[i]-add);
}
else if(a[i]<l.top()-add) {
ll tp=l.top(); l.pop();
tp-=add;
ans+=tp-a[i];
tp-=add;
r.push(tp);
l.push(a[i]+add);
l.push(a[i]+add);
}
else {
l.push(a[i]+add);
r.push(a[i]-add);
}
add+=h;
}
cout << ans;
}
/*
2 1
3 7
4 1
4 3 2 1
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |