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
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdint.h>
#include <set>
#include <tuple>

using namespace std;

struct piekarnik
{
public:
    int index;
    int czas_piecz;
    int64_t suma_czekania;

    piekarnik(){}
    piekarnik (int czas, int ind)
        :  index(ind), czas_piecz(czas), suma_czekania(0){}

    static bool cmp_index (const piekarnik & a, const piekarnik & b)
                          {return a.index < b.index;}
    static bool cmp_czas (const piekarnik & a, const piekarnik & b)
                          {return a.czas_piecz < b.czas_piecz;}
};

template <class T>
vector<T> wczytaj_dane(int ile)
{
    vector<T> dane(ile, 0);
    for (int ii=0; ii<ile; ii++)
    {
        T dana_ii;
        cin>>dana_ii;
        dane[ii] = dana_ii;
    }
    return dane;
}

vector<piekarnik> wczytaj_piek(int ile)
{
    vector<piekarnik> piek(ile);
    for (int ii=0; ii<ile; ii++)
    {
        int dana_ii;
        cin>>dana_ii;
        piek[ii] = piekarnik(dana_ii, ii);
    }
    return piek;
}


bool cmp_greater (const int i, const int j)
{
    return (i>j);
}


int64_t sumuj_czekanie(const vector<int64_t> & czasy_przyjscia,
                       int czas_piecz)
{
    int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia
    int64_t suma_czek = 0;
    for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++)
    {
        int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca;
        if (zapas_czasu < czas_piecz)
        {
            int64_t czekanie = czas_piecz - zapas_czasu;
            suma_czek += czekanie;
            czas_konca = czasy_przyjscia[ii] + czekanie;
        }
        else
            czas_konca = czasy_przyjscia[ii]; // czekanie = 0
    }
    return suma_czek;
}


pair<int64_t,int64_t> suma_czekania_i_skok(const vector<int64_t> & czasy_przyjscia,
                                       int czas_piecz)
{
    int64_t czas_konca = 0; // czas skonczenia ostatniego pieczenia
    int64_t suma_czek = 0;
    int64_t skok = 0;
    int licznik = 0; // liczy numer klienta od ostatniego nie czekajacego
    for (uint32_t ii=0; ii<czasy_przyjscia.size(); ii++)
    {
        int64_t zapas_czasu = czasy_przyjscia[ii] - czas_konca;
        if (zapas_czasu < czas_piecz)
        {
            int64_t czekanie = czas_piecz - zapas_czasu;
            suma_czek += czekanie;
            czas_konca = czasy_przyjscia[ii] + czekanie;
            licznik++;
            skok += licznik;
        }
        else // czekanie = 0
        {
            czas_konca = czasy_przyjscia[ii];
            licznik = 0;
        }
    }
    return make_pair(suma_czek, skok);
}

///////////////////////////////////////////
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // wczytanie danych
    int ile_klientow, ile_piekar;
    cin>>ile_klientow;
    cin>>ile_piekar;
    vector<int64_t> czasy_przyjscia = wczytaj_dane<int64_t>(ile_klientow);
    vector<piekarnik> czasy_pieczenia = wczytaj_piek(ile_piekar);

//    // obliczenie sumy czekania
//    for (auto iter = czasy_pieczenia.begin(); iter != czasy_pieczenia.end(); ++iter)
//    {
//        int64_t suma_czekania = sumuj_czekanie(czasy_przyjscia, *iter);
//        cout<<suma_czekania <<endl;
//    }

    // utworzenie zbioru wartosci czasu pieczenia dla ktorych nowy klient zaczyna czekac
    set<int64_t> zmiany;
    zmiany.insert(czasy_przyjscia[0]+1);
    for (auto iter = next(czasy_przyjscia.begin()); iter != czasy_przyjscia.end(); ++iter)
    {
        int64_t war1 = *iter - *prev(iter); // odleglosc od poprzedniego klienta
        int64_t war2 = *iter / (iter - czasy_przyjscia.begin() + 1); // czas na zapiekanke przy nieprzerwanym pieczeniu
        int64_t pocz_czekania = 1 + min(war1, war2);
        zmiany.insert(pocz_czekania);
    }

    // sortowanie czasow pieczenia - rosnaco
    sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_czas);

    //zliczanie sum czekania
    int64_t suma_dla_ost_zmiany = 0;
    int64_t skok = 0;
    int64_t ost_zmiana = 0;
    set<int64_t>::iterator      it_zmia = zmiany.begin();
    vector<piekarnik>::iterator it_piek = czasy_pieczenia.begin();

    while (it_piek != czasy_pieczenia.end())
    {
        while (it_piek != czasy_pieczenia.end()
               &&  (it_zmia == zmiany.end() || it_piek->czas_piecz < *it_zmia))
        {
            int64_t suma_dla_piek = suma_dla_ost_zmiany + skok *(it_piek->czas_piecz - ost_zmiana);
            it_piek->suma_czekania = suma_dla_piek;
            ++it_piek;
        }

        while (it_piek != czasy_pieczenia.end() && it_zmia != zmiany.end()
               &&  it_piek->czas_piecz >= *it_zmia) // pomijanie pustych przedzialow
        {
            ++it_zmia;
        }

        // nowe wartosci sumy dla zmiany, skoku itp
        ost_zmiana = *(prev(it_zmia));
        tie(suma_dla_ost_zmiany, skok) = suma_czekania_i_skok(czasy_przyjscia, ost_zmiana);
    }

    sort(czasy_pieczenia.begin(), czasy_pieczenia.end(), piekarnik::cmp_index);
    for (auto it = czasy_pieczenia.begin(); it!= czasy_pieczenia.end(); ++it)
    {
        cout<<it->suma_czekania <<endl;
    }

    return 0;
}