#include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<functional> #include<ctype.h> #include<map> #define LL long long #define LD long double #define L(x) ((x).size()) #define FI first #define SE second #define MP make_pair #define PB push_back using namespace std; struct cut{ LL b,d; int s; }; int n,m,last,x,y,z; LL b,d,dd,act,score; LL tab[501000]; LL sum[501000]; LL getSum(int a,int b){ return sum[b]-sum[a-1]; } vector<cut> S; cut h; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%lld",&tab[i]); } sort(tab+1,tab+n+1); for(int i=1;i<=n;++i){ sum[i] = sum[i-1]+tab[i]; } h.b = h.d = 0; h.s = 1; S.PB(h); while(m--){ scanf("%lld%lld",&d,&b); score = 0; last = n+1; while(!S.empty()){ h = S.back(); dd = d-h.d; act = h.b+dd*tab[h.s]; if(act>b){ score+=getSum(h.s,last-1)*dd; score+=(h.b-b)*(last-h.s); last = h.s; S.pop_back(); } else break; } if(!S.empty()){ h = S.back(); x = h.s; y = last-1; while(x!=y){ z = (x+y)/2; dd = d-h.d; act = h.b+dd*tab[z]; if(act>b) y = z; else x = z+1; } act = h.b+dd*tab[x]; if(act<=b)++x; else{ score+= getSum(x,last-1)*dd; score+= (h.b-b)*(last-x); } last = x; } if(last<=n){ h.b = b; h.d = d; h.s = last; S.PB(h); } printf("%lld\n",score); } }
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 | #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<string> #include<functional> #include<ctype.h> #include<map> #define LL long long #define LD long double #define L(x) ((x).size()) #define FI first #define SE second #define MP make_pair #define PB push_back using namespace std; struct cut{ LL b,d; int s; }; int n,m,last,x,y,z; LL b,d,dd,act,score; LL tab[501000]; LL sum[501000]; LL getSum(int a,int b){ return sum[b]-sum[a-1]; } vector<cut> S; cut h; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%lld",&tab[i]); } sort(tab+1,tab+n+1); for(int i=1;i<=n;++i){ sum[i] = sum[i-1]+tab[i]; } h.b = h.d = 0; h.s = 1; S.PB(h); while(m--){ scanf("%lld%lld",&d,&b); score = 0; last = n+1; while(!S.empty()){ h = S.back(); dd = d-h.d; act = h.b+dd*tab[h.s]; if(act>b){ score+=getSum(h.s,last-1)*dd; score+=(h.b-b)*(last-h.s); last = h.s; S.pop_back(); } else break; } if(!S.empty()){ h = S.back(); x = h.s; y = last-1; while(x!=y){ z = (x+y)/2; dd = d-h.d; act = h.b+dd*tab[z]; if(act>b) y = z; else x = z+1; } act = h.b+dd*tab[x]; if(act<=b)++x; else{ score+= getSum(x,last-1)*dd; score+= (h.b-b)*(last-x); } last = x; } if(last<=n){ h.b = b; h.d = d; h.s = last; S.PB(h); } printf("%lld\n",score); } } |