#include <iostream> #include <queue> #include <algorithm> #include <vector> using namespace std; #define PII pair<long long, long long> #define PIP pair<long long, PII> #define pb push_back #define MP make_pair #define ll long long #define int long long int n,m; ll poczatek[300000]; ll przyrost[300000]; ll dozlaczenia[300000]; ll typki[300000]; ll answer[300000]; ll pref[300000]; int last[300000]; int R[300000]; priority_queue< PIP, vector<PIP>, greater<PIP> >Q; vector<PII>V; void read(){ cin>>n>>m; typki[1] = 1; last[1] = 1; R[1] = 1; for(int i=2;i<=n+1;i++){ cin>>poczatek[i]; pref[i] = pref[i-1] + poczatek[i]; typki[i] = 1; dozlaczenia[i] = poczatek[i] - poczatek[i-1]; R[i] = i; last[i] = i; Q.push( MP( dozlaczenia[i], MP(i-1,i) ) ); } for(int i=0;i<m;i++){ int q; cin>>q; V.pb(MP(q,i)); } sort(V.begin(),V.end()); } int find(int a){ if( R[a] != a ) R[a] = find(R[a]); return R[a]; } void solve(){ ll tim = 0, new_tim = 0, plus = 0, new_plus = 0, res = 0; int it = 0; int xx=0; while(!Q.empty()){ while( it < (int)V.size() && Q.top().first > V[it].first){ ll q = V[it].first; int nr = V[it].second; answer[nr] = (q-tim)*plus + res; //cout<<nr<<" ans "<<answer[nr]<<endl; it++; } new_tim = Q.top().first; while( !Q.empty() && Q.top().first <= new_tim ) { //ll tmp_tim = Q.top().first; int a = Q.top().second.first; int b = Q.top().second.second; Q.pop(); if( find(a) == a && find(b) == b ){ //cout<<a<< " LACE "<<b<<endl; res -= poczatek[a] * typki[a] + przyrost[a] * tim - pref[last[a]] + pref[a-1]; res -= poczatek[b] * typki[b] + przyrost[b] * tim - pref[last[b]] + pref[b-1]; R[b] = a; last[a] = last[b]; typki[a] += typki[b]; plus -= przyrost[a]; plus -= przyrost[b]; przyrost[a] = ((typki[a]-1)*typki[a])/2; new_plus += przyrost[a]; res += poczatek[a] * typki[a] + przyrost[a] * new_tim - pref[last[a]] + pref[a-1]; //cout<<res<<" res"<<endl; b = last[a]+1; if( b <= n+1 ){ ll licznik = poczatek[b] - new_tim - (poczatek[a] + new_tim * ( typki[a] - 1 ) ); ll mianownik = typki[a]; ll d = licznik/mianownik; if( licznik % mianownik != 0 && licznik >= 0) d++; Q.push(MP(new_tim+d,MP(a,b))); //cout<<licznik<<" lm "<<mianownik<<endl; //cout<<a<<" ab "<<b<<" "<<new_tim+d<<endl; } } } res += (new_tim-tim)*plus; plus += new_plus; tim = new_tim; new_plus = 0; xx++; //cout<<res<<"RES"<<endl; //cout<<endl; } for(;it<(int)V.size();it++){ ll q = V[it].first; int nr = V[it].second; answer[nr] = (q-tim)*plus + res; } } void write(){ for( int i = 0; i < m; i++ ){ cout<<answer[i]<<endl; } } main(){ ios_base::sync_with_stdio(false); read(); solve(); write(); }
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <queue> #include <algorithm> #include <vector> using namespace std; #define PII pair<long long, long long> #define PIP pair<long long, PII> #define pb push_back #define MP make_pair #define ll long long #define int long long int n,m; ll poczatek[300000]; ll przyrost[300000]; ll dozlaczenia[300000]; ll typki[300000]; ll answer[300000]; ll pref[300000]; int last[300000]; int R[300000]; priority_queue< PIP, vector<PIP>, greater<PIP> >Q; vector<PII>V; void read(){ cin>>n>>m; typki[1] = 1; last[1] = 1; R[1] = 1; for(int i=2;i<=n+1;i++){ cin>>poczatek[i]; pref[i] = pref[i-1] + poczatek[i]; typki[i] = 1; dozlaczenia[i] = poczatek[i] - poczatek[i-1]; R[i] = i; last[i] = i; Q.push( MP( dozlaczenia[i], MP(i-1,i) ) ); } for(int i=0;i<m;i++){ int q; cin>>q; V.pb(MP(q,i)); } sort(V.begin(),V.end()); } int find(int a){ if( R[a] != a ) R[a] = find(R[a]); return R[a]; } void solve(){ ll tim = 0, new_tim = 0, plus = 0, new_plus = 0, res = 0; int it = 0; int xx=0; while(!Q.empty()){ while( it < (int)V.size() && Q.top().first > V[it].first){ ll q = V[it].first; int nr = V[it].second; answer[nr] = (q-tim)*plus + res; //cout<<nr<<" ans "<<answer[nr]<<endl; it++; } new_tim = Q.top().first; while( !Q.empty() && Q.top().first <= new_tim ) { //ll tmp_tim = Q.top().first; int a = Q.top().second.first; int b = Q.top().second.second; Q.pop(); if( find(a) == a && find(b) == b ){ //cout<<a<< " LACE "<<b<<endl; res -= poczatek[a] * typki[a] + przyrost[a] * tim - pref[last[a]] + pref[a-1]; res -= poczatek[b] * typki[b] + przyrost[b] * tim - pref[last[b]] + pref[b-1]; R[b] = a; last[a] = last[b]; typki[a] += typki[b]; plus -= przyrost[a]; plus -= przyrost[b]; przyrost[a] = ((typki[a]-1)*typki[a])/2; new_plus += przyrost[a]; res += poczatek[a] * typki[a] + przyrost[a] * new_tim - pref[last[a]] + pref[a-1]; //cout<<res<<" res"<<endl; b = last[a]+1; if( b <= n+1 ){ ll licznik = poczatek[b] - new_tim - (poczatek[a] + new_tim * ( typki[a] - 1 ) ); ll mianownik = typki[a]; ll d = licznik/mianownik; if( licznik % mianownik != 0 && licznik >= 0) d++; Q.push(MP(new_tim+d,MP(a,b))); //cout<<licznik<<" lm "<<mianownik<<endl; //cout<<a<<" ab "<<b<<" "<<new_tim+d<<endl; } } } res += (new_tim-tim)*plus; plus += new_plus; tim = new_tim; new_plus = 0; xx++; //cout<<res<<"RES"<<endl; //cout<<endl; } for(;it<(int)V.size();it++){ ll q = V[it].first; int nr = V[it].second; answer[nr] = (q-tim)*plus + res; } } void write(){ for( int i = 0; i < m; i++ ){ cout<<answer[i]<<endl; } } main(){ ios_base::sync_with_stdio(false); read(); solve(); write(); } |