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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<ios>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

using namespace std;

/** Maskymalny czas pieczenia */
const int dMax=1000000;
/** Maksymalny czas przyjścia klienta do kolejki */
const int64_t timeMax=1000000000000;

/** Liczba klientów */
int n;
/** Liczba piekarników */
int m;

/**
 * Pomocnicza struktura określająca piekarnik
 */
struct Oven {
    /** Czas pieczenia jednej zapiekanki */
    int d;
    /** Obliczony wynik */
    int64_t res;
};

/** Komparator dla piekarników */
bool OvenCmp(Oven* a, Oven *b) {
    return a->d<b->d;
}

/** Czasy przyjścia klientów */
int64_t t[200002];
/** Informacje o piekarnikach */
Oven d[200001];
/** Posortowane informacje o piekarnikach */
Oven* sd[200001];

/**
 * Klasa okreslająca grupę klientów, którzy na siebie wpadaja.
 */
class Group {
public:
    /** Następna grupa */
    Group *next=NULL;
    /** Czy grupa została wchłonięta w inną */
    bool deleted=false;
    /** Pierwszy klient należący do tej grupy */
    int i;
    /** Czas przyjścia pierwszego klienta */
    int64_t enter;
    /** Liczba dodatkowych klientów w tej grupie (poza pierwszym) */
    int k=0;
    /** Łączny czas przyjść klientów dla tej grupy, poza pierwszym, czyli: t[i+1]+...+t[i+k] */
    int64_t ti=0;

    int growTime;

    /** Współczynnik przesunięcia - k*ti */
    int64_t kti() { return (int64_t)k*enter; }

    /** Współczynnik skali */
    int64_t mul() { return ((int64_t)k*((int64_t)k+1))/2; }

    /** Czas rozrośnięcia się tej grupy (przejęcia następnej) */
    void calcGrowTime() {
        if(next==NULL) {
            growTime=dMax+1;
            return;
        }   // to ostatni element, więc za nim nic nie ma, więc się już nie rozrośnie
        /** Czas pomiędzy pierwszy klientem tej grupy, a następnej */
        int64_t dist=next->enter-enter;
        if(k==0) {  // jeżeli grupa jednoosobowa
            growTime=(int)min(dist, (int64_t)dMax+1);   // odległość pomiędzy klientami
        } else {
            // jeżeli grupa liczniejsza, to w sumie to samo tylko że powyżej nie ma dzielenia
            growTime = (int)min((int64_t)dMax + 1, dist / (k + 1));
        }
    }

    /** Połączenie tej grupy z następną */
    void grow() {
        Group* t=next;
        next=t->next;   // poprawamy wskaźnik na kolejną
        k+=t->k+1;  // aktualizujemy liczbę osób w tej grupie +1 bo doliczamy pierwszego klienta kolejnej grupy
        ti+=t->ti+t->enter; // dodajemy czas przyjść klientów oraz pierwszego klienta z kolejnej grupy
		t->deleted=true;	// oznaczamy, ze usuniety (wcielony), aby nie byl kolejny raz przetwarzany z kolejki
        calcGrowTime(); // aktualizujemy czas połączenia z następną grupą
    }
};

class GroupCmp {
public:
    bool operator() (Group* a, Group* b) {
        return a->growTime > b->growTime;
    }
};

Group groups[200001];
priority_queue<Group*, vector<Group*>, GroupCmp> groupsQueue;

/** Łączny czas przyjść klientów dla wszystkich grup, poza prezentantem, czyli suma Group.ti */
int64_t tiTotal=0;
/** Łączny współczynnik przesunięcia dla wszystkich grup, czyli suma Grup.kti */
int64_t ktiTotal=0;
/** Łączny współczynnik skali */
int64_t mulTotal=0;

/**
 * Funkcja obliczająca wynik dla zadanego czasu pieczenia
 */
int64_t processForTime(int d) {
    // etap 1 - zaktualizowanie grup
    while(groupsQueue.top()->growTime<d) { // powiększamy wszystkie grupy, których czas rośnięcia jest dla danego czasu pieczenia
        Group* g=groupsQueue.top();
        groupsQueue.pop();
        if(g->deleted) continue;    // pomijamy
        Group* n=g->next;

        // usuwamy z głównego wzoru składniki usuwanej grupy oraz aktualizowanej grupy
        tiTotal-=g->ti; tiTotal-=n->ti;
        ktiTotal-=g->kti(); ktiTotal-=n->kti();
        mulTotal-=g->mul(); mulTotal-=n->mul();

        g->grow();  // pochłąnięcie grupu
        // zaktualizowanie wzoru o nowe wartości
        tiTotal+=g->ti;
        ktiTotal+=g->kti();
        mulTotal+=g->mul();
        // na koniec wrzucamy do kolejki, aby dalej mogła grupa rosnąć
        groupsQueue.push(g);
    }
    // jak już zaktualizowały się grupy, a w zasadzie to główny wzór to wyliczamy wynik
    return ktiTotal-tiTotal+mulTotal*(int64_t)d;
}

int main(int argc, char** argv) {
    // przyspiszenie cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // odczytujemy dane wejściowe
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>t[i];
    for(int i=0;i<m;++i) {
        d[i].res=0;
        cin>>d[i].d;
        sd[i]=&d[i];
    }
    // sortujemy piekarniki od najszybszego
    sort(sd, sd+m, OvenCmp);

    // grupa zerowa to terminator, dla czasu 0
    groups[0].enter=0;
    groups[0].i=0;
    // Inicujemy grupy
    for(int i=0;i<n;++i) {
        groups[i+1].enter=t[i];
        groups[i+1].i=i;
        groups[i].next=&groups[i+1];    // łączymy listę
    }
    // obliczamy czas łączenia się grup z kolejnymi
    for(int i=0;i<=n;++i) {
        groups[i].calcGrowTime();
        groupsQueue.push(&groups[i]);
    }
    // przetwarzami pierkarniki od najszybszego
    for(int i=0;i<m;++i) {
        Oven* o=sd[i];
        o->res=processForTime(o->d);
    }

    /** Wypisujemy uzyskane wyniki według pierwotnej kolejności */
    for(int i=0;i<m;++i) {
        cout<<d[i].res<<endl;
    }

    return 0;
}