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 `#include using namespace std; #define REP(i,n) for(int i=0;i<(n);++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(c) ((int)(c).size()) #define MAXN 200000 typedef long long ll; ll t[MAXN]; int d[MAXN]; ll ans[MAXN]; int idxd[MAXN]; int n,m; struct dst { ll d; int num; int nxt; typedef pair pli; bool operator<(const dst& oth){ if(d == LLONG_MAX) return false; if(oth.d == LLONG_MAX) return true; return pli(d*oth.num,nxt) < pli(oth.d*num,oth.nxt); } } dist[MAXN]; int merge(int a){ int b = dist[a].nxt; if(dist[b].d == LLONG_MAX) dist[a].d = LLONG_MAX; else dist[a].d += dist[b].d; dist[a].num += dist[b].num; dist[a].nxt = dist[b].nxt; return b; } bool overlap(int a, int k){ const dst& d = dist[a]; return d.d <= (ll)k*d.num; } ll sq(int a){ const dst& d = dist[a]; if(d.d == LLONG_MAX) return (ll)d.num*(d.num+1)/2; return (ll)d.num*(d.num-1)/2; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; REP(i,n) cin>>t[i]; REP(i,n+1) { if(i == 0) dist[i] = dst{t[i],1,1}; else if(i == n) dist[i] = dst{LLONG_MAX,0,-1}; else dist[i] = dst{t[i]-t[i-1],1,i+1}; } REP(i,m) cin>>d[i]; REP(i,m) idxd[i]=i; const auto cmp = [](int a, int b){return dist[a] < dist[b];}; set ds(cmp); REP(i,n+1) ds.insert(i); ll ssq=0; int psize=0; int besttotal=INT_MAX; sort(idxd, idxd+m, [](int a, int b){return d[a]1 && overlap(*ds.begin(), lst)){ int t = *ds.begin(); ds.erase(ds.begin()); ssq -= sq(t); dst old = dist[t]; int k = merge(t); ssq += sq(t) - sq(k); ds.erase(k); ll np = (dist[k].d == LLONG_MAX ? dist[k].num+1 : dist[k].num); calc += np*((ll)old.num*lst - old.d); ds.insert(t); } ans[idxd[i]] = calc; } REP(i,m) cout<