#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200002; const ll inf = 1e15; ll t[N]; ll ts[N]; ll ans[N]; ll fa = 0, fb = 0; struct ev; map<int, ev> bg; struct ev { int a, b; ll pr; bool r; void upd(int x) { ll n = b - a; fa += n * (n - 1) / 2 * x; fb += (n * t[a] - ts[b-1] + ts[a-1]) * x; } static ev line(int a) { ev e; e.a = a; e.b = bg.upper_bound(a)->first; e.r = false; int n = e.b - e.a; e.pr = (t[e.b] - t[e.a] + n - 1) / n; return e; } static ev req(int d, int nr) { ev e; e.a = d; e.b = nr; e.r = true; e.pr = e.a; return e; } }; bool operator<(const ev &a, const ev &b) { return make_pair(a.pr, a.r) > make_pair(b.pr, b.r); } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lld", t + i); ts[i] = t[i] + ts[i-1]; } t[n+1] = inf; bg[n+1] = ev(); priority_queue<ev> pq; for(int i = n; i >= 0; i--) { bg[i] = ev::line(i); bg[i].upd(1); pq.push(bg[i]); } for(int i = 0; i < m; i++) { int d; scanf("%d", &d); pq.push(ev::req(d, i)); } while(!pq.empty()) { auto e = pq.top(); pq.pop(); if(e.r) ans[e.b] = fa * e.a + fb; else { if(!bg.count(e.a) || e.b == n+1) continue; bg[e.a].upd(-1); bg[e.b].upd(-1); bg.erase(e.b); bg[e.a] = ev::line(e.a); bg[e.a].upd(1); pq.push(bg[e.a]); } } for(int i = 0; i < m; i++) printf("%lld\n", ans[i]); }
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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200002; const ll inf = 1e15; ll t[N]; ll ts[N]; ll ans[N]; ll fa = 0, fb = 0; struct ev; map<int, ev> bg; struct ev { int a, b; ll pr; bool r; void upd(int x) { ll n = b - a; fa += n * (n - 1) / 2 * x; fb += (n * t[a] - ts[b-1] + ts[a-1]) * x; } static ev line(int a) { ev e; e.a = a; e.b = bg.upper_bound(a)->first; e.r = false; int n = e.b - e.a; e.pr = (t[e.b] - t[e.a] + n - 1) / n; return e; } static ev req(int d, int nr) { ev e; e.a = d; e.b = nr; e.r = true; e.pr = e.a; return e; } }; bool operator<(const ev &a, const ev &b) { return make_pair(a.pr, a.r) > make_pair(b.pr, b.r); } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lld", t + i); ts[i] = t[i] + ts[i-1]; } t[n+1] = inf; bg[n+1] = ev(); priority_queue<ev> pq; for(int i = n; i >= 0; i--) { bg[i] = ev::line(i); bg[i].upd(1); pq.push(bg[i]); } for(int i = 0; i < m; i++) { int d; scanf("%d", &d); pq.push(ev::req(d, i)); } while(!pq.empty()) { auto e = pq.top(); pq.pop(); if(e.r) ans[e.b] = fa * e.a + fb; else { if(!bg.count(e.a) || e.b == n+1) continue; bg[e.a].upd(-1); bg[e.b].upd(-1); bg.erase(e.b); bg[e.a] = ev::line(e.a); bg[e.a].upd(1); pq.push(bg[e.a]); } } for(int i = 0; i < m; i++) printf("%lld\n", ans[i]); } |