//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vpl vector<pll>
#define vvpl vector<vpl>
#define vl vector<ll>
#define vvl vector<vl>
//#define x first
//#define y second
using namespace std;
const int N = 1e6 + 9, LGV = 33, LGN = 21, Mod = 1e9 + 7;
//const int Inf = 0x3f3f3f3f;
const ll Inf = LLONG_MAX / 2;
const bool test_case = false;
//ifstream fin("landscape.in");
//ofstream fout("landscape.out");
//#define cin fin
//#define cout fout
int n, h, a[N];
ll ans = 0;
ll addl = 0, addr = 0;
priority_queue<int> l;
priority_queue<int, vi, greater<>> r;
ll value = 0;
///move to left
void shl()
{
ll t = r.top() + addr;
ans += abs(value - t);
r.pop();
l.push(t - addl);
}
///move to right
void shr()
{
ll t = l.top() + addl;
ans += abs(value - t);
l.pop();
r.push(t - addr);
}
void show()
{
vi v;
while(!l.empty())
{
v.pb(l.top() + addl);
l.pop();
}
reverse(v.begin(), v.end());
for(auto e : v)cout << e << ' ';
cout << " | ";
for(auto e : v)l.push(e - addl);
v.clear();
while(!r.empty())
{
cout << r.top() + addr << ' ';
v.pb(r.top() + addr);
r.pop();
}
cout << '\n';
for(auto e : v)r.push(e - addr);
}
void solve()
{
cin >> n >> h;
FOR(i, 1, n)cin >> a[i];
FOR(i, 1, n)
{
addl -= h, addr += h;
value = a[i];
// cout << "\n";
// show();
// cout << " | | | \n";
if(l.empty() || a[i] <= l.top() + addl){
l.push(a[i] - addl);
l.push(a[i] - addl);
shr();
}
else{
r.push(a[i] - addr);
r.push(a[i] - addr);
shl();
}
// show();
// cout << '\n';
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
if(test_case)cin >> t;
while(t --)solve();
return 0;
}
# | 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... |