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
#include <stdint.h>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;

/****************************************************************************************************************/

struct Segment {
    uint64_t t, size;
    Segment *next;
    uint32_t id;
    int32_t last_d;

    const bool will_merge_before(const uint64_t numerator, const uint64_t denominator, const uint64_t fallback) const {
        uint64_t factor_this = (this->next->t - this->t) * denominator;
        uint64_t factor_other = numerator * (this->size + 1);
        if (factor_this != factor_other) return factor_this < factor_other;
        return (this->t) < fallback;
    }

    const bool will_merge_before(const Segment &other) const {
        return will_merge_before(other.next->t - other.t, other.size + 1, other.t);
    }

    const bool will_merge_before(const uint64_t d) const {
        return will_merge_before(d, 1, 0);
    }

    uint64_t square(){ return size * (size + 1) / 2; }
    Segment(uint64_t T = 0, int _id = -1):t(T),size(0),id(_id),next(0),last_d(-1){}
};

struct SegmentComparator {
    bool operator() (Segment *x, Segment *y) const {
        return x->will_merge_before(*y);
    }
};

/****************************************************************************************************************/

uint32_t n, m;
vector<uint64_t> T;
vector<uint32_t> D;
vector<Segment*> S;
set<Segment*, SegmentComparator> Q;
map<uint32_t, vector<uint32_t> > M;
vector<uint64_t> result;

int main() {
    scanf("%u %u", &n, &m);
    T.resize(n+1); D.resize(m);
    for (int i=1; i<=n; ++i) scanf("%llu", &T[i]);
    for (int i=0; i<m; ++i) scanf("%u", &D[i]);
    T[0] = 0; ++n;

    result.resize(m);
    for (int i=0; i<m; ++i) M[D[i]].push_back(i);

    S.resize(n);
    for (int i=0; i<n; ++i) {
        S[i] = new Segment(T[i], i);
        if (i>0) {
            S[i-1]->next = S[i];
            Q.insert(S[i-1]);
        }
    }

    int64_t current_delay = 0, current_squares = 0, last_d = 0;
    while (!M.empty()) {
        uint64_t current_d = M.begin()->first;
        vector<uint32_t> res_pos = M.begin()->second;
        M.erase(M.begin());

        int64_t last_squares = current_squares;
        while (!Q.empty() && (*Q.begin())->will_merge_before(current_d)) {
            Segment *s = *Q.begin();
            Segment *rot = s->next;
            Q.erase(s);
            if (rot->next) Q.erase(rot);
            current_delay += (rot->size + 1) * ((s->size + 1)*current_d + s->t - rot->t);
            current_squares -= s->square() + rot->square();
            s->size += rot->size + 1;
            current_squares += s->square();
            s->next = rot->next;
            if (rot->next) Q.insert(s);
            delete rot;
        }

        current_delay += (last_squares) * (current_d - last_d);
        last_d = current_d;
        for(int i=0; i<res_pos.size(); ++i) result[res_pos[i]] = current_delay;
    }

    for(int i=0; i<m; ++i) printf("%llu\n", result[i]);
}