結果
問題 | No.2169 To Arithmetic |
ユーザー |
👑 |
提出日時 | 2022-12-21 01:02:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 2,526 bytes |
コンパイル時間 | 2,146 ms |
コンパイル使用メモリ | 211,336 KB |
最終ジャッジ日時 | 2025-02-09 17:47:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> // #include<atcoder/all> using namespace std; // using namespace atcoder; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward<Tail>(tail)...); } template<typename T> void print(vector<T> &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template<typename T, typename S> void prisep(vector<T> &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template<typename T> void print(vector<vector<T>> &A){ for(auto &row: A) print(row); } void solve(){ int n, Q; cin >> n >> Q; vector<ll> A(n), D(n); for(int i = 0; i < n; i++){ cin >> A[i]; if(i != 0) D[i] = A[i - 1] - A[i]; } vector<pair<ll, int>> query(Q); for(int i = 0; i < Q; i++){ cin >> query[i].first; query[i].second = i; } vector<ll> ans(Q); sort(query.begin(), query.end()); vector<ll> DD = D; DD[0] = -1LL << 60; sort(DD.begin(), DD.end(), greater<ll>()); int dind = 0; ll tot = 0; ll cnt = 0; for(auto tmp:query){ ll d = tmp.first; int i = tmp.second; while(DD[dind] + d >= 0){ cnt++; tot += DD[dind]; dind++; } ans[i] = tot + cnt * d; } for(int i = 1; i < n; i++) D[i] += D[i - 1]; auto cross3=[&](pair<ll, ll> &A, pair<ll, ll> &B, pair<ll, ll> &C){ return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) *(C.first - A.first); }; vector<pair<ll, ll>> qs; qs.push_back({0, D[0]}); qs.push_back({1, D[1]}); int sz = 2; for(int i = 2; i < n; i++){ ll d = D[i]; pair<ll, ll> P = {i, d}; while(sz >= 2 && (cross3(qs[sz - 1], qs[sz - 2], P)) >= 0){ qs.pop_back(); sz--; } qs.push_back(P); sz++; if(i == n - 1){ qs.push_back(P); } } int ind = 0; sz--; reverse(query.begin(), query.end()); for(auto tmp:query){ ll d = tmp.first; int i = tmp.second; while(ind < sz){ ll dx = qs[ind + 1].first - qs[ind].first; ll dy = qs[ind + 1].second - qs[ind].second; if(-d * dx > dy) ind++; else break; } ans[i] -= qs[ind].first * d + qs[ind].second; } prisep(ans, endl); } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); }