結果

問題 No.2169 To Arithmetic
コンテスト
ユーザー lam6er
提出日時 2025-03-31 18:00:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 5,100 ms
コンパイル使用メモリ 204,628 KB
実行使用メモリ 9,476 KB
最終ジャッジ日時 2025-03-31 18:02:11
合計ジャッジ時間 7,865 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;

struct Line {
    mutable ll m, b, p;
    bool operator<(const Line& o) const { return m < o.m; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { 
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->m == y->m) x->p = x->b > y->b ? inf : -inf;
        else x->p = div(y->b - x->b, x->m - y->m);
        return x->p >= y->p;
    }
    void add(ll m, ll b) {
        auto z = insert({m, b, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.m * x + l.b;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    vector<ll> A(n);
    for(int i=0; i<n; i++) {
        cin >> A[i];
    }
    vector<ll> a;
    for(int i=1; i < n; i++) {
        a.push_back(A[i] - A[i-1]);
    }
    sort(a.begin(), a.end());
    vector<ll> prefix = {0};
    for(ll num : a) {
        prefix.push_back(prefix.back() + num);
    }
    
    LineContainer lc;
    for(int j = n-1; j >=0; j--) {
        ll m = -j;
        ll b = A[j];
        lc.add(m, b);
    }
    
    while(q--) {
        ll d;
        cin >> d;
        ll M = lc.query(d);
        int count = upper_bound(a.begin(), a.end(), d) - a.begin();
        ll sum = prefix[count];
        ll sum_max_d = d * count - sum;
        ll ans = (M - A[0]) + sum_max_d;
        cout << ans << '\n';
    }
    return 0;
}
0