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
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int N=2*1e5+5;
const long long INF=1e18;
long long n, m, pop[N], nast[N];
long long t[N], an[N];
struct piekarnik
{
        long long d, id;
};
piekarnik d[N];
bool cmp1(piekarnik x, piekarnik y)
{
        return x.d<y.d;
}
bool cmp2(piekarnik x, piekarnik y)
{
        return x.id<y.id;
}
typedef pair<long long, long long> P;
struct cmp
{
        bool operator()(P x, P y)
        {
                if(x.first==y.first) return x.second<y.second;
                return x.first<y.first;
        }
};
long long dod(long long x, long long y)
{
        long long ans=(t[x]-t[y])/(x-y);
        ans+=1;
        return ans;
}
long long aryt(long long d)
{
        return (d*(d+1))/2;
}
set<P,cmp> S;
int main()
{
        scanf("%lld%lld", &n, &m);
        t[n+1]=INF;
        for(int i=1;i<=n;i++)
        {
                scanf("%lld", &t[i]);
                pop[i]=i-1;
                nast[i]=i+1;
                S.insert(make_pair(t[i]-t[i-1]+1,i));
        }
        S.insert(make_pair(INF-t[n],n+1));
        for(int i=1;i<=m;i++)
        {
                scanf("%lld", &d[i].d);
                d[i].id=i;
        }
        sort(d+1,d+m+1,cmp1);
        long long il=0, ans=0;
  long long ost=0;
        for(int i=1;i<=m;i++)
        {
                while((*S.begin()).first<=d[i].d)
                {
                        long long x=(*S.begin()).first;
                        long long y=(*S.begin()).second;
                        S.erase(S.begin());
                        ans+=(x-ost)*il;
                        ans+=(t[pop[y]]+x*(y-pop[y])-t[y])*(nast[y]-y);
                        ost=x;
                        long long nas=nast[y];
                        long long popo=pop[y];
                        S.erase(make_pair(dod(nas,y),nas));
                        pop[nas]=popo;
                        nast[popo]=nas;
                        S.insert(make_pair(dod(nas,popo),nas));
                        il-=aryt(nas-y);
                        il-=aryt(y-popo);
                        il+=aryt(nas-popo);
                }
                ans+=(d[i].d-ost)*il;
                ost=d[i].d;
                an[d[i].id]=ans;
        }
        for(int i=1;i<=m;i++) printf("%lld\n", an[i]);
        return 0;
}