結果
問題 |
No.2169 To Arithmetic
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }