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
#include <bits/stdc++.h>
using namespace std;
int n, m, d[200200];
bool polaczony[200200];
long long wynik, zmiana;
long long t[200200], ile[200200], w[2000200];
const long long DUZA_LICZBA = 1e13;
long long MAX_PIEC = 0;

struct czas
{
    int id;
    long long czas;
    long long dodaj;
};
priority_queue<czas> PQ;

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

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

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

inline void dodaj_nowy(long long id, long long ile)
{
    czas nowy;
    nowy.id    = id;
    nowy.dodaj = (t[id + ile] - t[id]) % ile;
    nowy.czas  = (t[id + ile] - t[id]) / ile;
    PQ.push(nowy);
}

inline void aktualizuj(long long ile1, long long ile2, long long ile3, long long wyrownanie)
{
    zmiana -= ile1 * (ile1 - 1) / 2;
    zmiana -= ile2 * (ile2 - 1) / 2;
    wynik  -= ile2 * wyrownanie; //naprawa przypadku gdy grupy nachodzą na siebie
    zmiana += ile3 * (ile3 - 1) / 2;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>t[i];
        ile[i] = 1;
    }
    for(int i = 0; i < m; i++)
    {
        cin>>d[i];
        MAX_PIEC = max((long long) d[i], MAX_PIEC);
    }

    //Brzegowi klienci
    ile[0] = 1;
    t[n+1] = DUZA_LICZBA;

    //Pierwsze różnice
    for(int i = 0; i < n; i++)
    {
        czas pom;
        pom.id = i;
        pom.czas = t[i+1] - t[i];
        pom.dodaj = 0;
        PQ.push(pom);
    }

    //Obliczenie wyniku
    for(int piec = 1; piec <= MAX_PIEC + 10; piec++)
    {
        while(!PQ.empty() && PQ.top().czas < piec)
        {
            czas C = PQ.top();
            PQ.pop();

            if(polaczony[C.id]) continue;

            //Łączenie grup
            long long ile1 = ile[C.id];
            long long ile2 = ile[C.id + ile1];
            long long ile3 = ile1 + ile2;

            polaczony[C.id + ile1] = true;
            ile[C.id] = ile3;

            //Aktualizacja zmiany wyniku
            aktualizuj(ile1, ile2, ile3, C.dodaj);

            //Tworzenie nowej grupy i wrzucenie do kolejki
            dodaj_nowy(C.id, ile3);
        }
        wynik += zmiana;
        w[piec] = wynik;
    }
    //Wypisanie wyniku
    for(int piec = 0; piec < m; piec++)
    {
        cout<<w[d[piec]]<<endl;
    }
}