基地台與房屋仲介 (wifi2)

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

#define ALL(x) begin(x), end(x)
#define SZ(x) ((int)(x).size())

const int INF = INT_MAX >> 1;

struct Line {
    int h, p, c;
    Line(int _h = 0, int _p = 0, int _c = 0) {h = _h, p = _p, c = _c;}
    /// 取位置 x 的值（下取整） ///
    int operator() (int x) {return c * h / (abs(x-p) + c);}
    /// 取位置 x 的值（分數） ///
    pair<int, int> get_val(int x) {return {c * h, abs(x-p) + c};}
};

/// 求香蕉位置（分數） ///
pair<int, int> banana(Line a, Line b) {
    // assert(a.h < b.h and a.p > b.p);
    return {b.h * a.p - b.p * a.h - b.h + a.h, b.h - a.h};
}

/// 比較分數大小 ///
bool cmp_le(pair<int, int> a, pair<int, int> b) {
    if (a.first / a.second != b.first / b.second) return a.first / a.second < b.first / b.second;
    a.first %= a.second, b.first %= b.second;
    /// banana 回傳的分子是 O(NB)、分母是 O(B)，如果沒有上面的處理可能會爆 long long ///
    return a.first * b.second <= b.first * a.second;
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N, C; cin >> N >> C;

    vector<int> B(N);
    for (int &x : B) cin >> x;

    vector<int> A(N, 0);

    for (int _ : {0, 1}) {
        deque<Line> deq{Line(0, -1, C)};

        for (int i = 0; i < N; ++i) {
            while (SZ(deq) >= 2 and cmp_le(deq[0].get_val(i), deq[1].get_val(i))) deq.pop_front();
            A[i] = max(A[i], deq[0](i));
            if (deq[0](i) >= B[i]) continue;

            Line now(B[i], i, C);
            while (SZ(deq) and deq[0].h <= now.h) deq.pop_front();
            while (SZ(deq) >= 2 and cmp_le(banana(deq[0], deq[1]), banana(now, deq[0]))) deq.pop_front();
            deq.emplace_front(now);
        }

        reverse(ALL(A)), reverse(ALL(B));
    }

    // for (int i = 0; i < N; ++i) cout << A[i] << " \n"[i == N-1];

    for (int i = 0; i < N; ++i) {
        if (A[i] > B[i]) return cout << "No" << "\n", 0;
    }
    cout << "Yes" << "\n";
    for (int i = 0; i < N; ++i) {
        cout << (A[i] == B[i] ? 0 : B[i]) << " \n"[i == N-1];
    }

    return 0;
}