#include <cstdio> #include <algorithm> using namespace std; int n,m,i,p,t=1,le,ri,h,a[500500]; long long x,y,r,b[500500],c[500500],d[500500],s[500500]; int main() { scanf("%d%d",&n,&m); b[t]=n; for (i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); reverse(a+1,a+n+1); for (i=1; i<=n; i++) s[i]=s[i-1]+a[i]; while (m--) { scanf("%lld%lld",&x,&y); for (r=p=0; t>0 && a[b[t]]*(x-d[t])+c[t]>=y; t--) { r+=(s[b[t]]-s[p])*(x-d[t])+(c[t]-y)*(b[t]-p); p=b[t]; } if (t>0) { le=p; ri=b[t]; while (p<ri) { h=(p+ri)/2+1; if (a[h]*(x-d[t])+c[t]>=y) p=h; else ri=h-1; } r+=(s[ri]-s[le])*(x-d[t])+(c[t]-y)*(ri-le); } b[++t]=p; c[t]=y; d[t]=x; printf("%lld\n",r); } 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 | #include <cstdio> #include <algorithm> using namespace std; int n,m,i,p,t=1,le,ri,h,a[500500]; long long x,y,r,b[500500],c[500500],d[500500],s[500500]; int main() { scanf("%d%d",&n,&m); b[t]=n; for (i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); reverse(a+1,a+n+1); for (i=1; i<=n; i++) s[i]=s[i-1]+a[i]; while (m--) { scanf("%lld%lld",&x,&y); for (r=p=0; t>0 && a[b[t]]*(x-d[t])+c[t]>=y; t--) { r+=(s[b[t]]-s[p])*(x-d[t])+(c[t]-y)*(b[t]-p); p=b[t]; } if (t>0) { le=p; ri=b[t]; while (p<ri) { h=(p+ri)/2+1; if (a[h]*(x-d[t])+c[t]>=y) p=h; else ri=h-1; } r+=(s[ri]-s[le])*(x-d[t])+(c[t]-y)*(ri-le); } b[++t]=p; c[t]=y; d[t]=x; printf("%lld\n",r); } return 0; } |