結果
問題 | No.2169 To Arithmetic |
ユーザー | hotman78 |
提出日時 | 2022-12-24 17:18:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 2,139 bytes |
コンパイル時間 | 2,952 ms |
コンパイル使用メモリ | 217,992 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2024-11-18 05:24:27 |
合計ジャッジ時間 | 11,768 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 6 ms
5,248 KB |
testcase_05 | AC | 4 ms
5,248 KB |
testcase_06 | AC | 5 ms
5,248 KB |
testcase_07 | AC | 7 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 116 ms
5,248 KB |
testcase_10 | AC | 90 ms
7,296 KB |
testcase_11 | AC | 209 ms
5,504 KB |
testcase_12 | AC | 50 ms
6,528 KB |
testcase_13 | AC | 196 ms
7,936 KB |
testcase_14 | AC | 109 ms
5,632 KB |
testcase_15 | AC | 56 ms
7,040 KB |
testcase_16 | AC | 115 ms
5,504 KB |
testcase_17 | AC | 298 ms
5,248 KB |
testcase_18 | AC | 144 ms
5,248 KB |
testcase_19 | AC | 399 ms
7,808 KB |
testcase_20 | AC | 406 ms
7,936 KB |
testcase_21 | AC | 394 ms
7,808 KB |
testcase_22 | AC | 400 ms
7,936 KB |
testcase_23 | AC | 400 ms
7,808 KB |
testcase_24 | AC | 327 ms
7,936 KB |
testcase_25 | AC | 339 ms
5,376 KB |
testcase_26 | AC | 334 ms
7,808 KB |
testcase_27 | AC | 337 ms
7,808 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);++i) #define all(n) (n).begin(),(n).end() using lint=long long; /** * Author: Simon Lindholm * Date: 2017-04-20 * License: CC0 * Source: own work * Description: Container where you can add lines of the form kx+m, and query maximum values at points x. * Useful for dynamic programming (``convex hull trick''). * Time: O(\log N) * Status: stress-tested */ using ll=long long; struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { auto z = insert({k, m, 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.k * x + l.m; } }; int main(){ cin.tie(0)->sync_with_stdio(0); lint n,q; cin>>n>>q; vector<lint>a(n); rep(i,0,n)cin>>a[i]; map<lint,lint>memo; LineContainer lc; rep(i,0,n)lc.add(-i,a[i]); lint sum=0; rep(i,0,n)sum+=a[i]; vector<lint>dd(n-1); rep(i,1,n)dd[i-1]+=a[i]-a[i-1]; sort(all(dd)); vector<lint>dsum(n); rep(i,0,n-1)dsum[i+1]=dd[i]+dsum[i]; while(q--){ lint d; cin>>d; if(memo.count(d)){ cout<<memo[d]<<endl; continue; } lint mn=1LL<<60; lint x=lc.query(d); auto e=lower_bound(all(dd),d)-dd.begin(); lint ans=(d*e-dsum[e])+((dsum.back()-dsum[e])-d*(n-1-e)); cout<<(ans+abs(x+(n-1)*d-a.back())+abs(a[0]-x))/2<<endl; } }