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
#include <stdio.h>
#include <queue>

//#define sufit(a, b) (((a)+(b)-1)/(b))

using namespace std;

struct czas
{
    long long czas; // czas jaki potrzeba do polaczenia grup
    int       indx; // index
    long long modulo;
};

inline bool operator<(const czas &a, const czas &b)
{
    return (a.czas > b.czas);
}

long long sufit(long long a, long long b)
{
    return (a + b - 1) / b;
}

int main(void)
{
    int n, m;
    static long long t[200002];
    static int       d[200000];
    static long long r[1000001];
    static int       s[200000]; // sklejone
    long long obecne_rozwiazanie;
    long long delta;
    priority_queue<czas> PQ;

    scanf("%d%d", &n, &m);

    s[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &t[i]);
        s[i] = 1;
    }
    t[n+1] = 1000000000000000000LL;
    for (int i = 0; i < m; i++)
        scanf("%d", &d[i]);

    r[0] = obecne_rozwiazanie = delta = 0;
    for (int i = 0; i < n; i++)
    {
        czas C;

        C.indx = i;
        C.czas = t[i+1] - t[i];
        C.modulo = 0;

        PQ.push(C);
    }

    for (int i = 1; i <= 1000000; i++)
    {
        while (!PQ.empty() && PQ.top().czas < i)
        {
            czas C = PQ.top();
            PQ.pop();

            if (s[C.indx] != -1)
            {
                int stare1 = s[C.indx];
                int stare2 = s[C.indx + s[C.indx]];

                obecne_rozwiazanie -= C.modulo * stare2;
                s[C.indx + s[C.indx]] = -1;
                s[C.indx] += stare2;


//printf("Czas z kolejki %lld\n", C.czas);
//printf("W czasie %d skleilem grupe %d, ma ona teraz dlugosc %d\n", i, C.indx, s[C.indx]);

                czas CN;

                CN.indx = C.indx;
                CN.czas = (t[C.indx + s[C.indx]] - t[C.indx]) / s[C.indx];
                CN.modulo = (t[C.indx + s[C.indx]] - t[C.indx]) % s[C.indx];

                PQ.push(CN);

                delta -= (long long) stare1 * (stare1 - 1) / 2;
                delta -= (long long) stare2 * (stare2 - 1) / 2;
                delta += (long long)(stare1 + stare2) * (stare1 + stare2 -1) / 2;
            }
        }

        obecne_rozwiazanie += delta;

        r[i] = obecne_rozwiazanie;
    }

    for (int i = 0; i < m; i++)
    {
        printf("%lld\n", r[d[i]]);
    }

    return 0;
}