#include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INNF = 1e18L + 1; const int IINNF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #undef LOCAL #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #define NN 4 #define MM 5 #else #define NN 200000 #define MM 1000000 #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif ll n, m; ll clients[NN + 1], par[NN + 1], len[NN + 1], ans[MM + 1]; vector<ll> to_proc[MM + 1]; ll anc(ll i){ if(i == par[i]){ return i; } else { return anc(par[i]); } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m; vector<pair<ll, ll> >hist = {{MM, 0}}; rep(i, 1, n + 1){ cin >> clients[i]; ll cnt = 0, pref = 0; while(SZ(hist)){ if(hist.back().ft == -1){ cnt+=hist.back().sd; hist.pop_back(); } else { ll wd = hist.back().ft, val = hist.back().sd; hist.pop_back(); if(val + (cnt + 1) * (pref + wd) <= clients[i]){ pref += wd; } else { ll wd1 = (clients[i] - val) / (cnt + 1) - pref; pref += wd1; if(wd - wd1){ hist.pb({wd - wd1, val}); } break; } } } if(pref + 1 <= MM){ hist.pb({-1, cnt + 1}); to_proc[pref + 1].pb(i); } if(pref){ hist.pb({pref, clients[i]}); } DBG(i, clients[i]); for(auto& p : hist){ cerr << "(" << p.ft << ", " << p.sd << ") "; } cerr << endl; } ll csum = 0; rep(i, 0, n + 1){ par[i] = i; len[i] = 1; csum += clients[i]; } ll s1 = csum, s2 = 0; rep(i, 1, MM + 1){ for(auto& c : to_proc[i]){ ll prv = anc(c - 1); ll l1 = len[prv], l2 = len[c]; s1 += (clients[prv] - clients[c]) * l2; s2 += (l1 + l2) * (l1 + l2 - 1) / 2 - l1 * (l1 - 1) / 2 - l2 * (l2 - 1) / 2; par[c] = prv; len[prv] = l1 + l2; DBG(i, c, s1, s2, prv, clients[prv], clients[c]); } ans[i] = s1 + i * s2 - csum; DBG(i, ans[i]); } rep(_, 0, m){ ll t1; cin >> t1; cout << ans[t1] << "\n"; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include<bits/stdc++.h> #define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++) #define all(v) (v).begin(), (v).end() #define SZ(v) (int)((v).size()) #define pb push_back #define ft first #define sd second typedef long long ll; typedef unsigned long long ull; typedef long double ld; const long long INNF = 1e18L + 1; const int IINNF = 1e9 + 1; using namespace std; template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...); } #undef LOCAL #ifdef LOCAL #define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #define NN 4 #define MM 5 #else #define NN 200000 #define MM 1000000 #define DBG(...) (__VA_ARGS__) #define cerr if(0)cout #endif ll n, m; ll clients[NN + 1], par[NN + 1], len[NN + 1], ans[MM + 1]; vector<ll> to_proc[MM + 1]; ll anc(ll i){ if(i == par[i]){ return i; } else { return anc(par[i]); } } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m; vector<pair<ll, ll> >hist = {{MM, 0}}; rep(i, 1, n + 1){ cin >> clients[i]; ll cnt = 0, pref = 0; while(SZ(hist)){ if(hist.back().ft == -1){ cnt+=hist.back().sd; hist.pop_back(); } else { ll wd = hist.back().ft, val = hist.back().sd; hist.pop_back(); if(val + (cnt + 1) * (pref + wd) <= clients[i]){ pref += wd; } else { ll wd1 = (clients[i] - val) / (cnt + 1) - pref; pref += wd1; if(wd - wd1){ hist.pb({wd - wd1, val}); } break; } } } if(pref + 1 <= MM){ hist.pb({-1, cnt + 1}); to_proc[pref + 1].pb(i); } if(pref){ hist.pb({pref, clients[i]}); } DBG(i, clients[i]); for(auto& p : hist){ cerr << "(" << p.ft << ", " << p.sd << ") "; } cerr << endl; } ll csum = 0; rep(i, 0, n + 1){ par[i] = i; len[i] = 1; csum += clients[i]; } ll s1 = csum, s2 = 0; rep(i, 1, MM + 1){ for(auto& c : to_proc[i]){ ll prv = anc(c - 1); ll l1 = len[prv], l2 = len[c]; s1 += (clients[prv] - clients[c]) * l2; s2 += (l1 + l2) * (l1 + l2 - 1) / 2 - l1 * (l1 - 1) / 2 - l2 * (l2 - 1) / 2; par[c] = prv; len[prv] = l1 + l2; DBG(i, c, s1, s2, prv, clients[prv], clients[c]); } ans[i] = s1 + i * s2 - csum; DBG(i, ans[i]); } rep(_, 0, m){ ll t1; cin >> t1; cout << ans[t1] << "\n"; } return 0; } |