#include<cstdio> #include<algorithm> #define e1 first #define e2 second using namespace std; long long sp,kp,pp,dp,lz,ss; long long zs,h,t1[1000000],d,t[1000000]; pair<pair<long long,long long>,pair<long long,long long> > stc[1000000]; bool can(){if(ss==0) return false;return h<=stc[ss-1].e2.e2+t[stc[ss-1].e1.e1]*(d-stc[ss-1].e2.e1);} void push(pair<pair<long long,long long>,pair<long long,long long> > e){stc[ss]=e;ss++;} int main() { scanf("%lld%lld",&dp,&lz); for(long long i=1;i<=dp;i++)scanf("%lld",&t[i]); sort(t+1,t+dp+1); for(long long i=1;i<=dp;i++)t1[i]=t1[i-1]+t[i]; push(make_pair(make_pair(1,dp),make_pair(0,0))); for(long long i=0;i<lz;i++) { scanf("%lld%lld",&d,&h); zs=0; while(can()) { pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1]; zs+=(p1.e1.e2-p1.e1.e1+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[p1.e1.e1-1])*(d-p1.e2.e1); ss--; } if(ss!=0) { pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1]; pp=p1.e1.e1;kp=p1.e1.e2+1; while(pp!=kp) { sp=((pp+kp)>>1); if(h>p1.e2.e2+t[sp]*(d-p1.e2.e1))pp=sp+1; else kp=sp; } stc[ss-1].e1.e2=pp-1; if(pp!=p1.e1.e2+1)zs+=(p1.e1.e2-pp+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[pp-1])*(d-p1.e2.e1); if(pp!=dp+1)push(make_pair(make_pair(pp,dp),make_pair(d,h))); } else { push(make_pair(make_pair(1,dp),make_pair(d,h))); } printf("%lld\n",zs); } }
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 | #include<cstdio> #include<algorithm> #define e1 first #define e2 second using namespace std; long long sp,kp,pp,dp,lz,ss; long long zs,h,t1[1000000],d,t[1000000]; pair<pair<long long,long long>,pair<long long,long long> > stc[1000000]; bool can(){if(ss==0) return false;return h<=stc[ss-1].e2.e2+t[stc[ss-1].e1.e1]*(d-stc[ss-1].e2.e1);} void push(pair<pair<long long,long long>,pair<long long,long long> > e){stc[ss]=e;ss++;} int main() { scanf("%lld%lld",&dp,&lz); for(long long i=1;i<=dp;i++)scanf("%lld",&t[i]); sort(t+1,t+dp+1); for(long long i=1;i<=dp;i++)t1[i]=t1[i-1]+t[i]; push(make_pair(make_pair(1,dp),make_pair(0,0))); for(long long i=0;i<lz;i++) { scanf("%lld%lld",&d,&h); zs=0; while(can()) { pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1]; zs+=(p1.e1.e2-p1.e1.e1+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[p1.e1.e1-1])*(d-p1.e2.e1); ss--; } if(ss!=0) { pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1]; pp=p1.e1.e1;kp=p1.e1.e2+1; while(pp!=kp) { sp=((pp+kp)>>1); if(h>p1.e2.e2+t[sp]*(d-p1.e2.e1))pp=sp+1; else kp=sp; } stc[ss-1].e1.e2=pp-1; if(pp!=p1.e1.e2+1)zs+=(p1.e1.e2-pp+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[pp-1])*(d-p1.e2.e1); if(pp!=dp+1)push(make_pair(make_pair(pp,dp),make_pair(d,h))); } else { push(make_pair(make_pair(1,dp),make_pair(d,h))); } printf("%lld\n",zs); } } |