結果
問題 | No.2169 To Arithmetic |
ユーザー | 👑 rin204 |
提出日時 | 2022-12-21 01:02:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 2,526 bytes |
コンパイル時間 | 2,668 ms |
コンパイル使用メモリ | 219,348 KB |
実行使用メモリ | 12,768 KB |
最終ジャッジ日時 | 2024-11-18 02:27:31 |
合計ジャッジ時間 | 7,030 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 3 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 31 ms
5,504 KB |
testcase_10 | AC | 49 ms
8,064 KB |
testcase_11 | AC | 62 ms
8,064 KB |
testcase_12 | AC | 34 ms
6,784 KB |
testcase_13 | AC | 74 ms
9,856 KB |
testcase_14 | AC | 40 ms
6,784 KB |
testcase_15 | AC | 41 ms
7,296 KB |
testcase_16 | AC | 40 ms
6,784 KB |
testcase_17 | AC | 79 ms
9,216 KB |
testcase_18 | AC | 40 ms
6,272 KB |
testcase_19 | AC | 118 ms
12,496 KB |
testcase_20 | AC | 120 ms
12,544 KB |
testcase_21 | AC | 117 ms
12,768 KB |
testcase_22 | AC | 115 ms
12,672 KB |
testcase_23 | AC | 116 ms
12,664 KB |
testcase_24 | AC | 89 ms
12,672 KB |
testcase_25 | AC | 77 ms
9,940 KB |
testcase_26 | AC | 94 ms
12,672 KB |
testcase_27 | AC | 101 ms
12,672 KB |
ソースコード
// #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();}