// PA2017, Zapiekanki 2 // Andrzej Pezarski #include <cstdio> #include <vector> #include <queue> using namespace std; struct Ziomek { long long t; int next; bool active; }; int N, M; Ziomek ziomek[210000]; long long res[210000]; long long sumaZ=0; long long sumaD=0; int main() { int N,M; scanf("%d%d", &N, &M); ziomek[0].t=0; ziomek[0].next=1; ziomek[0].active=true; for(int i=1; i<=N; i++) { scanf("%lld", &(ziomek[i].t)); ziomek[i].next=1; ziomek[i].active=true; } N++; priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > Q; for(int i=0; i<M; i++) { long long d; scanf("%lld", &d); Q.push(make_pair(d, i+N)); } for(int i=0; i<N-1; i++) { Q.push(make_pair(ziomek[i+1].t-ziomek[i].t, i)); } int resM=M; while(resM) { long long d=Q.top().first; int i=Q.top().second; Q.pop(); // printf("--> %lld %d %lld %lld\n", d, i, sumaD, sumaZ); if (i<N) { if (!ziomek[i].active) continue; int j=i+ziomek[i].next; ziomek[j].active=false; sumaD-=1LL*ziomek[i].next*(ziomek[i].next-1)/2; sumaD-=1LL*ziomek[j].next*(ziomek[j].next-1)/2; ziomek[i].next+=ziomek[j].next; sumaD+=1LL*ziomek[i].next*(ziomek[i].next-1)/2; sumaZ+=(ziomek[j].t-ziomek[i].t)*ziomek[j].next; j=i+ziomek[i].next; if (j<N) Q.push(make_pair((ziomek[j].t-ziomek[i].t)/(j-i)+1, i)); } else { i-=N; resM--; res[i]=sumaD*d- sumaZ; } } for(int i=0; i<M; i++) printf("%lld\n", res[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 | // PA2017, Zapiekanki 2 // Andrzej Pezarski #include <cstdio> #include <vector> #include <queue> using namespace std; struct Ziomek { long long t; int next; bool active; }; int N, M; Ziomek ziomek[210000]; long long res[210000]; long long sumaZ=0; long long sumaD=0; int main() { int N,M; scanf("%d%d", &N, &M); ziomek[0].t=0; ziomek[0].next=1; ziomek[0].active=true; for(int i=1; i<=N; i++) { scanf("%lld", &(ziomek[i].t)); ziomek[i].next=1; ziomek[i].active=true; } N++; priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > Q; for(int i=0; i<M; i++) { long long d; scanf("%lld", &d); Q.push(make_pair(d, i+N)); } for(int i=0; i<N-1; i++) { Q.push(make_pair(ziomek[i+1].t-ziomek[i].t, i)); } int resM=M; while(resM) { long long d=Q.top().first; int i=Q.top().second; Q.pop(); // printf("--> %lld %d %lld %lld\n", d, i, sumaD, sumaZ); if (i<N) { if (!ziomek[i].active) continue; int j=i+ziomek[i].next; ziomek[j].active=false; sumaD-=1LL*ziomek[i].next*(ziomek[i].next-1)/2; sumaD-=1LL*ziomek[j].next*(ziomek[j].next-1)/2; ziomek[i].next+=ziomek[j].next; sumaD+=1LL*ziomek[i].next*(ziomek[i].next-1)/2; sumaZ+=(ziomek[j].t-ziomek[i].t)*ziomek[j].next; j=i+ziomek[i].next; if (j<N) Q.push(make_pair((ziomek[j].t-ziomek[i].t)/(j-i)+1, i)); } else { i-=N; resM--; res[i]=sumaD*d- sumaZ; } } for(int i=0; i<M; i++) printf("%lld\n", res[i]); return 0; } |