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
#include <cstdio>
#include <list>
#include <unordered_set>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_COUNT = 200003;

struct Oven {
    int time;
    int index;
};

struct Group {
    int index_first;
    int index_last;
};

bool ovenscomp(Oven a, Oven b) { return a.time < b.time; }

inline long long int cumsum(int n) {
    if (n % 2 == 0) { return (long long int)n/2*(n+1); } else { return ((long long int)n+1)/2*n; }
}

bool should_extend(Group g, long long int* times, long long int* t_diffs, int n, int d) {
    if (g.index_last >= n) return false;
    int length = g.index_last - g.index_first;
    long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0;
    if (length == 0) {
        return (long long int)d > t_diffs[g.index_last];
    }
    return (length+1) * (long long int)d - (times[g.index_last-1] - t_prev) > t_diffs[g.index_last];
}

long long int delay(Group g, long long int* times, long long int* partial_times, int d) {
    int length = g.index_last - g.index_first;
    if (length == 0) return 0;
    long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0;
    return cumsum(length) * d - (partial_times[g.index_last] - partial_times[g.index_first]) + length * t_prev;
}

int n;  //number of clients
int m;  //number of ovens
long long int t[MAX_COUNT];	//times of clients arrival
Oven ovens[MAX_COUNT];   //ovens baking time
long long int min_diff;	//minimal difference of times of clients arrival
long long int t_diff[MAX_COUNT];	//differences of times of clients arrival
long long int part_times[MAX_COUNT];	//partial sums of times of clients arrival
Group groups[MAX_COUNT];
unordered_set<int> nonempty_groups;
long long int results[MAX_COUNT];   //results for particular ovens

int main(int argc, char *argv[]) {
    scanf("%d %d\n", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &t[i]);
	}
    scanf("\n");
    for (int i = 0; i < m; i++) {
        int ot;
		scanf("%d", &ot);
        ovens[i] = {ot, i};
	}
    sort(ovens, ovens+m, ovenscomp);
    min_diff = t[0];
    t_diff[0] = min_diff;
    for (int i = 1; i < n; i++) {
		t_diff[i] = t[i]-t[i-1];
        if (t_diff[i] < min_diff) min_diff = t_diff[i];
	}
    part_times[0] = 0;
    for (int i = 0; i < n; i++) {
        part_times[i+1] = part_times[i] + t[i];
    }
    
    for (int i = 0; i <= n; i++) {
        groups[i] = {i, i};
    }
    
    for (int c = 0; c < m; c++) {
        Oven d = ovens[c];
        long long int total = 0;
        if (d.time > min_diff) {
            
            int j = 0;
            while (j < n) {
                Group g = groups[j];
                if (should_extend(g, t, t_diff, n, d.time)) { //merging groups
                    nonempty_groups.erase(g.index_last+1);
                    nonempty_groups.insert(g.index_first);
                    g.index_last = groups[g.index_last+1].index_last;
                    groups[j] = g;
                } else {
                    j = g.index_last+1;
                }
            }
            
            for (unordered_set<int>::iterator it = nonempty_groups.begin(); it != nonempty_groups.end(); it++) {
                total += delay(groups[*it], t, part_times, d.time);
            }
            
        }
        
        results[d.index] = total;
    }
    for (int c = 0; c < m; c++) {
        printf("%lld\n", results[c]);
    }
    return 0;
}