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 <cassert>
#include <iostream>
#include <set>
#include <vector>
int main() {
std::cin.tie(NULL)->sync_with_stdio(false);
int n, h;
std::cin >> n >> h;
std::vector<int> m(2, 0);
std::vector<long long> x_shift(2, 0);
std::vector<long long> c(2, 0);
x_shift[0] = h, x_shift[1] = -h;
std::multiset<long long> m_changes[2]; // xpos for each m changes +1
for (int i = 0; i < n; i++) {
long long x;
std::cin >> x;
// shift by h
x_shift[0] -= h;
x_shift[1] += h;
c[0] += m[0] * h;
c[1] -= m[1] * h;
// append to line
m[0]--;
m[1]++;
m_changes[0].insert(x - x_shift[0]);
m_changes[1].insert(x - x_shift[1]);
// normalize
while (true) {
long long x_l = *m_changes[0].rbegin();
long long x_r = *m_changes[1].begin();
if (x_l + x_shift[0] <= x_r + x_shift[1]) {
break;
}
m_changes[0].erase(m_changes[0].find(x_l));
m_changes[1].erase(m_changes[1].find(x_r));
x_l += x_shift[0];
x_r += x_shift[1];
m_changes[0].insert(x_r - x_shift[0]);
m_changes[1].insert(x_l - x_shift[1]);
}
c[0] += x;
c[1] -= x;
}
while (!m_changes[1].empty()) {
// pop largest
long long x = *m_changes[1].rbegin();
m_changes[1].erase(m_changes[1].find(x));
// apply shift
x += x_shift[1];
// m*x + c = (m-1)*x + (x + c)
m[1]--;
c[1] += x;
}
assert(m[1] == 0);
std::cout << c[1] << std::endl;
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... |