#include <bits/stdc++.h> using namespace std; const int maxN = 200005, maxD = 1000001; const long long INF = 4000000000000000000LL; struct Client { long long t; int num; } T[maxN]; priority_queue <pair <long long, int> > H; long long res[maxD]; vector <int> inds; long long npo2(int n) { return 1LL * n * (n - 1) / 2; } inline void norm_H() { while (!H.empty() and T[-H.top().second].num == 0) H.pop(); } inline long long dt(int i) { return T[i + T[i].num].t - T[i].t; } long long f(int i) { return (dt(i) + T[i].num - 1) / T[i].num; } int main() { int n, m; scanf ("%d%d", &n, &m); T[0].num = 1; T[n + 1].t = INF; for (int i=1; i<=n; i++) { scanf ("%lld", &T[i].t); T[i].num = 1; } long long cost = 0, delta = 0; for (int i=n; i>=0; i--) { if (i > 0 and T[i - 1].t == T[i].t) { T[i - 1].num += T[i].num; T[i].num = 0; } else { delta += npo2(T[i].num); H.push(make_pair(-f(i), -i)); } } for (int d=0; d<maxD; ) { norm_H(); long long new_d = -H.top().first; while (true) { norm_H(); if (H.empty() or H.top().first != -new_d) break; inds.push_back(-H.top().second); H.pop(); } for (long long d_temp = d + 1; d_temp <= min(1LL*maxD-1, new_d); d_temp++) { cost += delta; res[d_temp] = cost; } if (new_d >= maxD) break; for (int v : inds) { if (T[v].num == 0) continue; while (dt(v) <= new_d * T[v].num) { int w = v + T[v].num; delta -= npo2(T[v].num); delta -= npo2(T[w].num); delta += npo2(T[v].num + T[w].num); long long x = (T[v].t + new_d * T[v].num - T[w].t) * T[w].num; cost += x; res[new_d] += x; T[v].num += T[w].num; T[w].num = 0; } H.push(make_pair(-f(v), -v)); } d = new_d; inds.resize(0); } while (m--) { int a; scanf ("%d", &a); printf("%lld\n", res[a]); } 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 113 114 115 | #include <bits/stdc++.h> using namespace std; const int maxN = 200005, maxD = 1000001; const long long INF = 4000000000000000000LL; struct Client { long long t; int num; } T[maxN]; priority_queue <pair <long long, int> > H; long long res[maxD]; vector <int> inds; long long npo2(int n) { return 1LL * n * (n - 1) / 2; } inline void norm_H() { while (!H.empty() and T[-H.top().second].num == 0) H.pop(); } inline long long dt(int i) { return T[i + T[i].num].t - T[i].t; } long long f(int i) { return (dt(i) + T[i].num - 1) / T[i].num; } int main() { int n, m; scanf ("%d%d", &n, &m); T[0].num = 1; T[n + 1].t = INF; for (int i=1; i<=n; i++) { scanf ("%lld", &T[i].t); T[i].num = 1; } long long cost = 0, delta = 0; for (int i=n; i>=0; i--) { if (i > 0 and T[i - 1].t == T[i].t) { T[i - 1].num += T[i].num; T[i].num = 0; } else { delta += npo2(T[i].num); H.push(make_pair(-f(i), -i)); } } for (int d=0; d<maxD; ) { norm_H(); long long new_d = -H.top().first; while (true) { norm_H(); if (H.empty() or H.top().first != -new_d) break; inds.push_back(-H.top().second); H.pop(); } for (long long d_temp = d + 1; d_temp <= min(1LL*maxD-1, new_d); d_temp++) { cost += delta; res[d_temp] = cost; } if (new_d >= maxD) break; for (int v : inds) { if (T[v].num == 0) continue; while (dt(v) <= new_d * T[v].num) { int w = v + T[v].num; delta -= npo2(T[v].num); delta -= npo2(T[w].num); delta += npo2(T[v].num + T[w].num); long long x = (T[v].t + new_d * T[v].num - T[w].t) * T[w].num; cost += x; res[new_d] += x; T[v].num += T[w].num; T[w].num = 0; } H.push(make_pair(-f(v), -v)); } d = new_d; inds.resize(0); } while (m--) { int a; scanf ("%d", &a); printf("%lld\n", res[a]); } return 0; } |