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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int roz=200000+4;
ll t[roz];
ll pref_t[roz];
int numery[roz]; //jakiej wartosci odpowiada numer
pair<ll,ll> wynik[2*roz]; //drzewo wynikow
void dodaj(int a,int b,int N,pair<ll,ll> x){
    while(true){
        if(a%2==1){wynik[a].first+=x.first;wynik[b].second+=x.second;a++;}
        if(b%2==0){wynik[b].first+=x.first;wynik[b].second+=x.second;b--;};
        if(a>b)break;
        a/=2;
        b/=2;
    }
    return;
}
ll odczyt(int x,int N,int d){
    x+=N;
    ll ret=0;
    while(x>0){
        ret+=ll(wynik[x].first*d+wynik[x].second);
        x/=2;
    };
    return ret;
};
ll nakoniec[(int)1e6+5];
int poczatek[2*roz];
int koniec[2*roz];
void wyp(int N){ //wypelnia tablice poczatkow i koncow
    for(int i=N;i<=2*N-1;i++){poczatek[i]=i;koniec[i]=i;}
    N--;
    while(N>0){
        poczatek[N]=poczatek[2*N];
        koniec[N]=koniec[2*N+1];
        N--;
    };
return;
};
ll tree[2*roz];
void replac(int wezel,int tree_od,int N){
 if(tree[wezel]==0 and wezel*2<N)tree[wezel]=tree_od;
        else{ //replace
            ll i=tree[wezel];
            ll n=tree_od;
            ll var1=((n-i)*(n-i-1))/2;
            ll var2=(n-i-1)*t[i] - (pref_t[n-1]-pref_t[i]);
            if(var1>0)dodaj(poczatek[wezel],koniec[wezel],N,make_pair(var1,var2));
            tree[wezel]=tree_od;
        }
    return;
}
void kopnij(int wezel,int N){ //lazy propagatio //dziala tylko gdy wezel<N
    if(tree[wezel]==0)return;
    replac(wezel*2,tree[wezel],N);
    replac(wezel*2+1,tree[wezel],N);
    tree[wezel]=0;
return;
}
void ustal(int a/*przedzial*/,int b,int wezel,int t_n/* jest numerem*/,int N){ //ustala wartosc w wezle //czyli ostatni przed ktorym sie wyrobil
   if(wezel>=N){replac(wezel,t_n,N);return;};
   kopnij(wezel,N);
   if(poczatek[wezel]==a and koniec[wezel]==b){tree[wezel]=t_n;return;}
   if(max(poczatek[2*wezel],a)<=min(koniec[2*wezel],b))    ustal(max(poczatek[2*wezel],a),min(koniec[2*wezel],b),wezel*2,t_n,N);
   if(max(poczatek[2*wezel+1],a)<=min(koniec[2*wezel+1],b))ustal(max(poczatek[2*wezel+1],a),min(koniec[2*wezel+1],b),wezel*2+1,t_n,N);
   return;
}
int znajdz(int num,int N){ //znajdzuje ostatnia pozycje na ktorej sie wyrobil
    num=num+N;
    int ost=0;
    while(num>0){
        ost=max(ll(ost),tree[num]);
        num/=2;
    }
    return ost;
};

int bin_search(int p,int q,int t_n,int N, vector<int> & d){//zwraca ostatni ktory sie ustatil
int s;
 while(p<q){
    s=(p+q+1)/2;
    int czy=znajdz(s,N); //ostatni na ktorym sie wyrobil
    ///czy sie wyrobil
    bool tak =( (t_n-czy)*d[s] <= t[t_n]-t[czy] )? 1:0;
    if(tak)p=s;
    else q=s-1;
 };
 return p;
}
main(){
ios_base::sync_with_stdio(false);
int n,m;
cin>>n>>m; //n klijenci
for(int i=1;i<=n;i++){cin>>t[i]; pref_t[i]=pref_t[i-1]+t[i];}
t[n+1]=2e18; pref_t[n+1]=2e18;
vector<int> d;
for(int i=1;i<=m;i++){
    int a;cin>>a;
    numery[i]=a;
    d.push_back(a);
};
sort(d.begin(),d.end());
int N=1;
while(N<n)N*=2;
wyp(N);
for(int i=1;i<=n;i++){
    int t_n=i;
    int x=bin_search(0,d.size()-1,t_n,N,d);//indeksowane od 0
        int czy=znajdz(x,N); //ostatni na ktorym sie wyrobil
        ///czy sie wyrobil
        bool tak =( (t_n-czy)*d[x] <= t[t_n]-t[czy] )? 1:0;
        if(tak==0)continue;
    ustal(0+N,x+N,1,i,N);
};
for(int i=0;i<m;i++)ustal(i+N,i+N,1,n+1,N);
for(int i=0;i<m;i++){ nakoniec[d[i]]=odczyt(i,N,d[i]);};
for(int i=1;i<=m;i++){cout<<nakoniec[ numery[i] ]<<"\n";}
return 0;
}