#include <stdio.h> #include <algorithm> #include <vector> int n,m; int A[500000+10]; long long B[500000+10]; long long d,b; struct typ { long long d,b; int l,r; // [l,r) long long cut(){ return d*A[l]-b; } long long cut(int L){ return d*A[L]-b; } }; std::vector<typ> stos; long long grass(int l,int r,long long d,long long b){ return d*(B[l]-B[r])-b*(r-l); } int search(int l,int p,long long d, long long b) // szuka elementu v w przedziale [l,p) { while (l<p) { int k = (l+p)/2; if (A[k]*d<=b) l=k+1; else p=k; } return l; } int q; int main(){ q=scanf("%d%d",&n,&m); for(int i=0;i<n;++i) q=scanf("%d",A+i); std::sort(A,A+n); A[n] = B[n] = 0; for(int i=n-1;i>=0;--i) B[i] = B[i+1]+A[i]; typ x; x.d = x.b = 0; x.l=0; x.r = n; stos.push_back(x); for(int i=0;i<m;++i){ q=scanf("%lld%lld",&d,&b); long long cur = 0; typ x ; x.d = d; x.b = b; x.l = n; x.r = n; while(!stos.empty() && stos.back().cut() < x.cut(stos.back().l)){ x.l = stos.back().l; cur += grass(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); stos.pop_back(); } if (!stos.empty()){ int j = search(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); if(j < stos.back().r){ cur += grass(j,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); stos.back().r = j; x.l = j; } } if (x.l < x.r) stos.push_back(x); printf("%lld\n",cur); } 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 | #include <stdio.h> #include <algorithm> #include <vector> int n,m; int A[500000+10]; long long B[500000+10]; long long d,b; struct typ { long long d,b; int l,r; // [l,r) long long cut(){ return d*A[l]-b; } long long cut(int L){ return d*A[L]-b; } }; std::vector<typ> stos; long long grass(int l,int r,long long d,long long b){ return d*(B[l]-B[r])-b*(r-l); } int search(int l,int p,long long d, long long b) // szuka elementu v w przedziale [l,p) { while (l<p) { int k = (l+p)/2; if (A[k]*d<=b) l=k+1; else p=k; } return l; } int q; int main(){ q=scanf("%d%d",&n,&m); for(int i=0;i<n;++i) q=scanf("%d",A+i); std::sort(A,A+n); A[n] = B[n] = 0; for(int i=n-1;i>=0;--i) B[i] = B[i+1]+A[i]; typ x; x.d = x.b = 0; x.l=0; x.r = n; stos.push_back(x); for(int i=0;i<m;++i){ q=scanf("%lld%lld",&d,&b); long long cur = 0; typ x ; x.d = d; x.b = b; x.l = n; x.r = n; while(!stos.empty() && stos.back().cut() < x.cut(stos.back().l)){ x.l = stos.back().l; cur += grass(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); stos.pop_back(); } if (!stos.empty()){ int j = search(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); if(j < stos.back().r){ cur += grass(j,stos.back().r,x.d-stos.back().d,x.b-stos.back().b); stos.back().r = j; x.l = j; } } if (x.l < x.r) stos.push_back(x); printf("%lld\n",cur); } return 0; } |