#include<cstdio> #include<algorithm> using namespace std; const int MN=500005; long long n, m, pros[2*MN], t1, t, b, t0, mpot, suma[4*MN], rownaj[4*MN], minek[4*MN], maksik[4*MN], takt[4*MN], wyn; int ros[2*MN]; void akt(int v, int dl){ int v1=2*v, v2=v1+1; rownaj[v1]=rownaj[v]; takt[v1]=takt[v]; suma[v1]=rownaj[v]*dl/2; minek[v1]=rownaj[v]; maksik[v1]=rownaj[v]; rownaj[v2]=rownaj[v]; takt[v2]=takt[v]; suma[v2]=rownaj[v]*dl/2; minek[v2]=rownaj[v]; maksik[v2]=rownaj[v]; rownaj[v]=-1; } void idz(int v, int vp, int vk){ if((v<mpot) && rownaj[v]!=-1) akt(v, vk-vp+1); suma[v]+=(pros[vk+1]-pros[vp])*(t1-takt[v]); minek[v]+=(t1-takt[v])*ros[vk+1]; maksik[v]+=(t1-takt[v])*ros[vp+1]; takt[v]=t1; //printf("jestem w %d %lld %lld %lld %lld %lld\n", v, suma[v], minek[v], maksik[v], takt[v], rownaj[v]); if(maksik[v]<=b){ //printf("nic %d\n", v); //tu nic nie ma return; } if(minek[v]>=b){ //printf("caly %d\n", v); //ucinamy caly wyn+=suma[v]-(vk-vp+1)*b; rownaj[v]=b; minek[v]=b; maksik[v]=b; suma[v]=(vk-vp+1)*b; return; } int v1=2*v, v2=v1+1; idz(v1, vp, (vp+vk)/2); idz(v2, (vp+vk+1)/2, vk); suma[v]=suma[v1]+suma[v2]; maksik[v]=maksik[v1]; //minek[v]=minek[v2]; } int main(){ int i, j, p, k, sr, a; scanf("%lld%lld", &n, &m); for(i=1; i<=n; i++){ scanf("%lld", &ros[i]); ros[i]=-ros[i]; } sort(ros+1, ros+n+1); for(int i=1; i<=n; i++){ ros[i]=-ros[i]; pros[i]=ros[i]+pros[i-1]; //printf("%lld ", pros[i]); } mpot=1; while(mpot<n) mpot=mpot<<1; //printf("mpot %lld\n", mpot); for(i=n+1; i<=mpot; i++) pros[i]=pros[i-1]; for(i=0; i<m; i++){ scanf("%lld%lld", &t1, &b); t=t1-t0; t0=t1; wyn=0; idz(1, 0, mpot-1); printf("%lld\n", wyn); } //scanf("%d", &i); 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 | #include<cstdio> #include<algorithm> using namespace std; const int MN=500005; long long n, m, pros[2*MN], t1, t, b, t0, mpot, suma[4*MN], rownaj[4*MN], minek[4*MN], maksik[4*MN], takt[4*MN], wyn; int ros[2*MN]; void akt(int v, int dl){ int v1=2*v, v2=v1+1; rownaj[v1]=rownaj[v]; takt[v1]=takt[v]; suma[v1]=rownaj[v]*dl/2; minek[v1]=rownaj[v]; maksik[v1]=rownaj[v]; rownaj[v2]=rownaj[v]; takt[v2]=takt[v]; suma[v2]=rownaj[v]*dl/2; minek[v2]=rownaj[v]; maksik[v2]=rownaj[v]; rownaj[v]=-1; } void idz(int v, int vp, int vk){ if((v<mpot) && rownaj[v]!=-1) akt(v, vk-vp+1); suma[v]+=(pros[vk+1]-pros[vp])*(t1-takt[v]); minek[v]+=(t1-takt[v])*ros[vk+1]; maksik[v]+=(t1-takt[v])*ros[vp+1]; takt[v]=t1; //printf("jestem w %d %lld %lld %lld %lld %lld\n", v, suma[v], minek[v], maksik[v], takt[v], rownaj[v]); if(maksik[v]<=b){ //printf("nic %d\n", v); //tu nic nie ma return; } if(minek[v]>=b){ //printf("caly %d\n", v); //ucinamy caly wyn+=suma[v]-(vk-vp+1)*b; rownaj[v]=b; minek[v]=b; maksik[v]=b; suma[v]=(vk-vp+1)*b; return; } int v1=2*v, v2=v1+1; idz(v1, vp, (vp+vk)/2); idz(v2, (vp+vk+1)/2, vk); suma[v]=suma[v1]+suma[v2]; maksik[v]=maksik[v1]; //minek[v]=minek[v2]; } int main(){ int i, j, p, k, sr, a; scanf("%lld%lld", &n, &m); for(i=1; i<=n; i++){ scanf("%lld", &ros[i]); ros[i]=-ros[i]; } sort(ros+1, ros+n+1); for(int i=1; i<=n; i++){ ros[i]=-ros[i]; pros[i]=ros[i]+pros[i-1]; //printf("%lld ", pros[i]); } mpot=1; while(mpot<n) mpot=mpot<<1; //printf("mpot %lld\n", mpot); for(i=n+1; i<=mpot; i++) pros[i]=pros[i-1]; for(i=0; i<m; i++){ scanf("%lld%lld", &t1, &b); t=t1-t0; t0=t1; wyn=0; idz(1, 0, mpot-1); printf("%lld\n", wyn); } //scanf("%d", &i); return 0; } |