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
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<cmath>
#define pb push_back
using namespace std;
typedef long long ll;

set<ll>s;
vector<ll>wej; //wejscie
vector<ll>zap; // zapytania
vector<ll>num; // po przenumerowaniu
ll kr[1000000]; //kropeczki
ll war[1000000]; //wartosci
ll n, q;

ll szukaj(ll x){
    ll l = -1, p = num.size()-1;
    while(p-l>1){
    ll s = l + (p-l)/2;
    if(num[s] == x) return s;
    if(num[s] < x) l = s;
    else p = s;
}
return p;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    long long pop = 0, ile=1;
    for(ll i=0; i<n; i++){
    long long a; cin >> a;
   //  cout << ceil((float)a/(float)ile) << " " << a-pop << endl;
    int t = min((ll)ceil((long double)a/(long double)ile), a-pop);
    t++; 
    ile++, pop = a;
    s.insert(t);
    s.insert(a);
    wej.pb(a);
    }
    
    for(ll i=0; i<q; i++){
    ll a; cin >> a;
    s.insert(a);
    zap.pb(a);
    }

    for(auto x : s) num.pb(x);
    pop=0, ile=1;
    for(auto x : wej){
        ll t = min((ll)ceil((long double)x/(long double)ile), x-pop);
        t++;
        t = szukaj(t);
        kr[t]++; ile++; pop=x;}
   
    ile=0;
    for(ll i=0; i<num.size(); i++)
    {
        ile+= (kr[i]*(kr[i]+1))/2;
        if(i!=0) war[i] = war[i-1]+ile*(num[i]-num[i-1]);
        else war[i] = ile;   
    }
    for(auto x : zap) cout << war[szukaj(x)] << endl;
}