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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <set>

using namespace std;
#define span_n(x, n) x, x+n
#define lint long long int

const int MaxN = 200003;
const int MaxM = 200003;

lint n, m;

lint T[MaxN];
lint MergeD[MaxN];
lint PrevToMerge[MaxN];
lint GroupCount[MaxN];

struct qComp
{
    bool operator () (lint ti1, lint ti2)
    {
        return MergeD[ti1] != MergeD[ti2]
            ? MergeD[ti1] < MergeD[ti2]
            : ti1 < ti2;
    }  
};
set<lint, qComp> Q;

lint D[MaxM];
lint Di[MaxM];
lint Results[MaxM];

void readInput();
void sortDi();
void initMergeD();
void initPrevToMerge();
void initGroupCount();
void initQ();

void writeResults();
lint sumSeq(lint from, lint to);
lint dkFromGroupMerge(lint n1, lint n2);
void setDMergeForNext(lint ti);

int main()
{
    readInput();
	sortDi();
    initMergeD();
    initPrevToMerge();
    initGroupCount();
	initQ();
    
    lint k = 0;
    for(lint i = 1; i <= m; ++i)
    {
        lint prev_d = D[Di[i-1]];
        lint d = D[Di[i]];
        lint dd = d - prev_d;
        
        lint dm = 0;
        lint dk = 0;
        while(!Q.empty() && MergeD[*Q.begin()] <= d)
        {
            lint ti = *Q.begin();
            Q.erase(Q.begin());
            
            dm += (T[ti] - T[PrevToMerge[ti]]) * GroupCount[ti];
            dk += dkFromGroupMerge(GroupCount[PrevToMerge[ti]], GroupCount[ti]);
            GroupCount[PrevToMerge[ti]] += GroupCount[ti];
            setDMergeForNext(PrevToMerge[ti]);
        }
        
        lint dp = dk * prev_d;
        k += dk;
        
        Results[Di[i]] = Results[Di[i-1]] - dm + dp + k*dd;
    }
    
    writeResults();
    
    return 0;
}

void readInput()
{
    scanf("%lld%lld", &n, &m);
    for(lint i = 1; i <= n; ++i)
        scanf("%lld", T+i);
    for(lint i = 1; i <= m; ++i)
        scanf("%lld", D+i);
}

void sortDi()
{
    iota(span_n(Di+1, m), 1);
    sort(span_n(Di+1, m), [](lint di1, lint di2)
    {
       return D[di1] < D[di2]; 
    });
}

void initMergeD()
{
    for(lint i = 1; i <= n; ++i)
        MergeD[i] = T[i] - T[i-1];
}

void initPrevToMerge()
{
    iota(span_n(PrevToMerge+1, n), 0);
}

void initGroupCount()
{
    fill_n(GroupCount, n+1, 1);
}

void initQ()
{
    for(lint i = 1; i <= n; ++i)
        Q.insert(i);
}

void writeResults()
{
    for(lint i = 1; i <= m; ++i)
        printf("%lld\n", Results[i]);
}

lint sumSeq(lint from, lint to)
{
    return (from+to)*(to-from+1)/2;
}

lint dkFromGroupMerge(lint n1, lint n2)
{
    return sumSeq(n1, n1+n2-1) - sumSeq(0, n2-1);
}

void setDMergeForNext(lint ti)
{
    lint next_ti = ti + GroupCount[ti];
    if(next_ti > n) return;
    PrevToMerge[next_ti] = ti;
    Q.erase(next_ti);
    MergeD[next_ti] = (T[next_ti] - T[ti] + GroupCount[ti] - 1) / GroupCount[ti];
    Q.insert(next_ti);
}