#include <cstdio> #include <algorithm> #include <stack> using namespace std; struct prz { int p,k; long long sum,ph,pd; }; int h[500005]; long long s[500005]; stack<prz> stos; int main() { int n,m,i,j; prz kaka; long long x,y,a,b,c,d,e,inf; scanf ("%d%d", &n, &m); for (i=1; i<=n; i++) scanf ("%d", &h[i]); sort(h+1,h+n+1); for (i=1; i<=n; i++) s[i]=s[i-1]+h[i]; kaka.p=1; kaka.k=n; kaka.pd=0; kaka.ph=0; kaka.sum=s[n]; stos.push(kaka); while (m--) { scanf ("%lld %lld", &x, &y); kaka=stos.top(); d=0; while (!stos.empty()) { kaka=stos.top(); stos.pop(); if (kaka.ph+(x-kaka.pd)*h[kaka.p]>=y) d+=(x-kaka.pd)*kaka.sum-(y-kaka.ph)*(kaka.k-kaka.p+1); else { if (kaka.ph+(x-kaka.pd)*h[kaka.k]<y) { stos.push(kaka); if (kaka.k!=n) { a=kaka.k+1; kaka.p=a; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]-s[a-1]; stos.push(kaka); } break; } a=kaka.p; b=kaka.k; while (a!=b) { c=(a+b)/2; if (kaka.ph+(x-kaka.pd)*(long long)h[c]>=y) b=c; else a=c+1; } d+=(x-kaka.pd)*(s[kaka.k]-s[a-1])-(y-kaka.ph)*(long long)(kaka.k-a+1); kaka.k=a-1; kaka.sum=s[a-1]-s[kaka.p-1]; stos.push(kaka); kaka.p=a; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]-s[a-1]; stos.push(kaka); break; } } if (stos.empty()) { kaka.p=1; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]; stos.push(kaka); } printf ("%lld\n", d); } 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 116 | #include <cstdio> #include <algorithm> #include <stack> using namespace std; struct prz { int p,k; long long sum,ph,pd; }; int h[500005]; long long s[500005]; stack<prz> stos; int main() { int n,m,i,j; prz kaka; long long x,y,a,b,c,d,e,inf; scanf ("%d%d", &n, &m); for (i=1; i<=n; i++) scanf ("%d", &h[i]); sort(h+1,h+n+1); for (i=1; i<=n; i++) s[i]=s[i-1]+h[i]; kaka.p=1; kaka.k=n; kaka.pd=0; kaka.ph=0; kaka.sum=s[n]; stos.push(kaka); while (m--) { scanf ("%lld %lld", &x, &y); kaka=stos.top(); d=0; while (!stos.empty()) { kaka=stos.top(); stos.pop(); if (kaka.ph+(x-kaka.pd)*h[kaka.p]>=y) d+=(x-kaka.pd)*kaka.sum-(y-kaka.ph)*(kaka.k-kaka.p+1); else { if (kaka.ph+(x-kaka.pd)*h[kaka.k]<y) { stos.push(kaka); if (kaka.k!=n) { a=kaka.k+1; kaka.p=a; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]-s[a-1]; stos.push(kaka); } break; } a=kaka.p; b=kaka.k; while (a!=b) { c=(a+b)/2; if (kaka.ph+(x-kaka.pd)*(long long)h[c]>=y) b=c; else a=c+1; } d+=(x-kaka.pd)*(s[kaka.k]-s[a-1])-(y-kaka.ph)*(long long)(kaka.k-a+1); kaka.k=a-1; kaka.sum=s[a-1]-s[kaka.p-1]; stos.push(kaka); kaka.p=a; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]-s[a-1]; stos.push(kaka); break; } } if (stos.empty()) { kaka.p=1; kaka.k=n; kaka.pd=x; kaka.ph=y; kaka.sum=s[n]; stos.push(kaka); } printf ("%lld\n", d); } return 0; } |