#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 5; int n, m, nast[N]; ll ans[N], t[N], kro[N]; pair<ll,int> d[N]; bool wyrzuc[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%lld", &t[i]); t[n] = 0; n++; for (int i = 0; i < m; i++) { scanf("%lld", &d[i].first); d[i].second = i; } sort(t, t+n); sort(d, d+m); ll minusy = 0, sumka = 0; priority_queue<pair<ll,int>> Q; for (int i = 0; i < n-1; i++) { kro[i] = 1; nast[i] = i+1; Q.push({-(t[i+1] - t[i] + 1), i}); } kro[n-1] = 1; for (int i = 0; i < m; i++) { while (!Q.empty() && -Q.top().first <= d[i].first) { int p = Q.top().second; Q.pop(); if (wyrzuc[p] || nast[p] == 0) continue; ll val = (t[nast[p]] - t[p]) / kro[p] + 1; if (val > d[i].first) continue; minusy += kro[nast[p]] * (t[nast[p]] - t[p]); sumka -= kro[p] * (kro[p] - 1) / 2LL; sumka -= kro[nast[p]] * (kro[nast[p]] - 1) / 2LL; wyrzuc[nast[p]] = 1; kro[p] += kro[nast[p]]; sumka += kro[p] * (kro[p] - 1) / 2LL; nast[p] = nast[nast[p]]; if (nast[p] != 0) Q.push({-((t[nast[p]] - t[p]) / kro[p] + 1), p}); } ans[d[i].second] = d[i].first * sumka - minusy; } for (int i = 0; i < m; i++) printf("%lld\n", ans[i]); 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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 5; int n, m, nast[N]; ll ans[N], t[N], kro[N]; pair<ll,int> d[N]; bool wyrzuc[N]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%lld", &t[i]); t[n] = 0; n++; for (int i = 0; i < m; i++) { scanf("%lld", &d[i].first); d[i].second = i; } sort(t, t+n); sort(d, d+m); ll minusy = 0, sumka = 0; priority_queue<pair<ll,int>> Q; for (int i = 0; i < n-1; i++) { kro[i] = 1; nast[i] = i+1; Q.push({-(t[i+1] - t[i] + 1), i}); } kro[n-1] = 1; for (int i = 0; i < m; i++) { while (!Q.empty() && -Q.top().first <= d[i].first) { int p = Q.top().second; Q.pop(); if (wyrzuc[p] || nast[p] == 0) continue; ll val = (t[nast[p]] - t[p]) / kro[p] + 1; if (val > d[i].first) continue; minusy += kro[nast[p]] * (t[nast[p]] - t[p]); sumka -= kro[p] * (kro[p] - 1) / 2LL; sumka -= kro[nast[p]] * (kro[nast[p]] - 1) / 2LL; wyrzuc[nast[p]] = 1; kro[p] += kro[nast[p]]; sumka += kro[p] * (kro[p] - 1) / 2LL; nast[p] = nast[nast[p]]; if (nast[p] != 0) Q.push({-((t[nast[p]] - t[p]) / kro[p] + 1), p}); } ans[d[i].second] = d[i].first * sumka - minusy; } for (int i = 0; i < m; i++) printf("%lld\n", ans[i]); return 0; } |