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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <string>
#include <sstream>
#include <vector>

using namespace std;
using lolo = long long;
using vlolo = vector< lolo >;
using vint = vector< int >;



struct Klaster {
	lolo pocz = 0;
	lolo krotnosc = 0;
	int kolejny = -1;
	lolo rabaty = 0;
	lolo dekor = 0;

	lolo nn1() const {
		// zakladamy, ze pierwszy gostek odbiera zapiekanke
		// w czasie 0, jesli nie bedzie gotowa, to powinnismy
		// byc dolaczeni do wczesniejszego klastra w ktorym
		// ten warunek jest spelniony (wyjatek -- pierwszy klaster)
		// wynika stad, ze ludki moga byc w jednym klastrze,
		// nawet jesli nie widza sie przy ladzie.
		return ( (this->krotnosc - 1) * this->krotnosc ) / 2;
	}

	void add( lolo czas ) {
		if( this->krotnosc == 0 ) {
			this->pocz = czas;
		}
		this->krotnosc += 1;
		this->rabaty += (czas - this->pocz );
	}

	lolo zasieg( lolo piekarnik ) {
		// -1 bo zakladam, ze pierwszy nie czeka
		// +1 bo zostawiam miejsce dla kolejnego
		return this->pocz + piekarnik * (this->krotnosc -1 +1);
	}

	lolo piekarnik_przedzerowy( lolo piekarnik)
	{
		return max( 0LL, piekarnik - this->pocz);
	}
};

struct Zliczenie {
	lolo nn1 = 0;
	lolo rabat = 0;
};

struct Piekarnik {
	int poz;
	lolo czas;
};

string tekst( Klaster const& k ) {
	stringstream sstr;
	//sstr << "[." << k.pocz << " " << k.krotnosc << "x ->" << k.kolejny << " " << k.dekor << "*]";
	sstr << "[." << k.pocz << " ";
	if( k.krotnosc == 0 ) {
		sstr << "__ ->";
	}
	else {
		sstr << k.krotnosc << "x ->";
	}
	sstr << k.kolejny << " " << k.dekor << "*]";
	return sstr.str();
}

string tekst( Zliczenie const& z ) {
	stringstream sstr;
	sstr << "( nn1 = " << z.nn1 << ", rabat = " << z.rabat << ")"; 
	return sstr.str();
}

string tekst( Piekarnik const& p ) {
	stringstream sstr;
	sstr << "(poz=" << p.poz << ", czas=" << p.czas << ")"; 
	return sstr.str();
}

template< typename T >
string tekst( vector< T > const& v ) {
	stringstream sstr;
	sstr << "[";
	// i < v.size() - 1
	//    dodaje 1 po obu stronach, bo size() jest unsigned!!
	for( int i = 0; i + 1 < v.size(); ++i ) {
		sstr << v[i] << " ";
	}
	if( v.size() > 0 ) { sstr << v[v.size() - 1]; }
	sstr << "]";
	return sstr.str();
}

template<>
string tekst< Klaster >( vector< Klaster > const& v ) {
	stringstream sstr;
	sstr << "-- klastry -- (" << endl;
	for( int i = 0; i < v.size(); ++i ) {
		sstr << "[" << setw(2) << i << "]" << tekst(v[i]) << endl;
	}
	sstr << ")" << endl;
	return sstr.str();
}

vlolo oblicz_opoznienia( vlolo const& czasy_przyjscia, lolo piekarnik ) {
	vlolo opoznienia( czasy_przyjscia.size() );

	lolo czas_wydania = 0;
	for( int i = 0; i < czasy_przyjscia.size(); ++i ) {
		lolo const& czas_przyjscia = czasy_przyjscia[i];
		czas_wydania = max( czas_wydania + piekarnik, czas_przyjscia );
		opoznienia[i] = max( 0LL, czas_wydania - czas_przyjscia );
	}

	return opoznienia;
}

vector< Klaster > przygotuj_klastry( vlolo czasy, vlolo opoznienia ) {
	int rozm = czasy.size();

	vector< Klaster > klastry( rozm );

	int k_rozm = 0;
	for( int i = 0; i < rozm; ++i ) {
		// zaczynam nowy klaster jesli 
		// -- nie ma opoznienia (czyli nie dokleilem sie do poprzedniego)
		// -- jestem pierwszym z listy
		if( (opoznienia[i] == 0) || (k_rozm == 0) ) {
			k_rozm += 1;
		}
		klastry[k_rozm - 1].add( czasy[i] );
	}

	assert( k_rozm > 0 );
	klastry.resize( k_rozm );
	for(int i = 0; i < klastry.size() - 1; ++i) {
		klastry[i].kolejny = i + 1;
	}
	klastry[ klastry.size() - 1 ].kolejny = -1;
	return klastry;
};

void dekoruj( Klaster& k1, Klaster const& k2 ) {
	// najwazniejsza f-ja
	// okreslamy przy jakiej dlugosci piekarnika laczymy sie z kolejnym klastrem
	// laczenie nastepuje, jesli pierwszy z kolejnego klastra po nas nie moze
	// przyjsc po gotowa zapiekanke (tzn. jego czas oczekiwania jest > 0)
	//
	// odleglosc 12, krotnosc 3 - potrzeba 4 - 1 = 3
	// odleglosc 11, krotnosc 3 - potrzeba 4 - 1 = 3
	// odleglosc 10, krotnosc 3 - potrzeba 4 - 1 = 3
	// odleglosc  9, krotnosc 3 - potrzeba 3 - 1 = 2
	
	// -1 bo pierwszy nie czeka + 1 bo musi zostac miejsce przed kolejnym klastrem
	// UWAGA: DLA PIERWSZEGO KLASTRA TRZEBA LICZYC INACZEJ!!!
	lolo x = k2.pocz - k1.pocz;
	lolo y = k1.krotnosc - 1 + 1; 
	k1.dekor = ( x + y - 1 ) / y; // ceiling bez castowania do float ( ceil(x/y) )
}

void dekoruj_Xxx( Klaster& k1, Klaster const& k2 ) {
	if( k1.krotnosc == 1 ) {
		k1.dekor = numeric_limits< lolo >::max() / 32;
	}
	else {
		lolo x = k2.pocz - k1.pocz;
		lolo y = k1.krotnosc - 1; 
		k1.dekor = ( x + y - 1 ) / y; // ceiling bez castowania do float ( ceil(x/y) )
	}
}

void dekoruj0( Klaster& k1, Klaster const& k2 )
{
	// odleglosc do poczatku >= odleglosci do kolejnego klastra
	// zatem mamy dosc miejsca z przodu
	if( k1.pocz >= k2.pocz - k1.pocz ) {
		dekoruj( k1, k2 );
		return;
	}

	lolo x = k2.pocz; // biore caly zakres od poczatku czasu
	lolo y = k1.krotnosc + 1; // nie mamy dosc miejsca, nie odejmuje 1 
	k1.dekor = ( x + y - 1 ) / y; // ceiling bez castowania do float ( ceil(x/y) )	
} 

void dekoruj_klastry( vector< Klaster >& klastry ) {
	int rozm = klastry.size();
	if( rozm == 0 ) { return; };
	if( rozm == 1 ) { klastry[0].dekor = numeric_limits< lolo >::max(); return; };

	dekoruj0( klastry[0], klastry[1] );
	for( int i = 1; i < rozm - 1; ++i ) {
		dekoruj( klastry[i], klastry[i+1] );
	}
	klastry[rozm - 1].dekor = numeric_limits< lolo >::max();
}

Zliczenie zliczaj_klastry( vector< Klaster >& klastry ) {
	Zliczenie z;

	for( auto&& k : klastry ) {
		z.nn1 += k.nn1();
		z.rabat += k.rabaty;
	}

	return z;
}

struct Sortownik {
	vector< Klaster > const& v;
	Sortownik( vector< Klaster > const& v ) : v(v) {};

	bool operator() ( int const& a, int const& b) {
		return this->v[a].dekor > v[b].dekor;
	}
};

void polacz_dwa( Klaster& k1, Klaster& k2 )
{
	k1.krotnosc += k2.krotnosc;
	k1.rabaty += k2.krotnosc * (k2.pocz - k1.pocz) + k2.rabaty;
	k1.kolejny = k2.kolejny;

	k2.krotnosc = 0; // zabity
	k2.rabaty = 0; // zabity
}

void odejmij_klaster( Zliczenie& z, Klaster const& k ) {
	z.nn1 -= k.nn1();
	z.rabat -= k.rabaty;
	assert( z.nn1 >= 0 );
	assert( z.rabat >= 0 );
}

void dodaj_klaster( Zliczenie& z, Klaster const& k ) {
	z.nn1 += k.nn1();
	z.rabat += k.rabaty;
}


vint scalaj_klastry( vector< Klaster >& klastry, vint do_scalenia, lolo const piekarnik, Zliczenie& zliczenie )
{
	vint scalone;

	sort( do_scalenia.begin(), do_scalenia.end(), greater< int >() );

	while( do_scalenia.size() ) {
		int const idx = do_scalenia.back(); do_scalenia.pop_back(); 

		Klaster& k = klastry[idx];
		//cerr << "    Scalanie [" << idx << "]" << tekst( k ) << endl;
		if( k.krotnosc == 0 ) {
			// mogl przyjsc zabity (zabilem przy poprzednim obrocie)
			// albo moglem ja zabic w trakcie aktualnego scalania
			// jest juz uwzglendiony w zliczeniu
			continue;
		}

		// w klastrze pierwszym moze nie byc spelniony warunek,
		// ze pierwszy przychodzi na gotowe. jesli nie jest
		// (piekarnik_przedzerowy > 0), to zasieg zwieksza sie
		// o czesc piekarnika, ktora wystaje przed zero 
		lolo korekta_zasiegu = (idx == 0) ? k.piekarnik_przedzerowy(piekarnik) : 0;
		//cerr << "    Korekta zasiegu " << korekta_zasiegu << endl;

		odejmij_klaster( zliczenie, k );
		
		scalone.push_back( idx );
		while( (k.kolejny != -1) && (k.zasieg(piekarnik) + korekta_zasiegu >= (klastry[k.kolejny].pocz)) ) {
			assert( klastry[k.kolejny].krotnosc > 0 );
			odejmij_klaster( zliczenie, klastry[k.kolejny] );
			polacz_dwa( k, klastry[k.kolejny] );
			if( k.kolejny == -1 ) {
				k.dekor = numeric_limits< lolo >::max();
			}
			else {
				if( idx == 0 ) {
					// TODO: jedna f-ja z dodatkowym argumentem
					dekoruj0( k, klastry[k.kolejny] );
				}
				else {
					dekoruj( k, klastry[k.kolejny] );
				}
			}
		}

		dodaj_klaster( zliczenie, k );
	}

	return scalone;
}

/*
lolo korekta1( Klaster const& k, lolo piekarnik  ) {
	return k.krotnosc * max(0LL, piekarnik - k.pocz );
}
*/

string tekst_stertowy( vint v, Sortownik& cmp ) // v przez wartosc!!!
{
	sort_heap( v.begin(), v.end(), cmp );
	reverse( v.begin(), v.end() );
	return tekst( v );
}

vlolo rozwiaz( vector< Klaster >& klastry, vector< Piekarnik > const& piekarniki ) {
	vector< lolo > wyniki( piekarniki.size() );
	vector< int > sterta( klastry.size() );
	//iota( sterta.begin() + 1, sterta.end(), 1 ); // hack, nie wkladam 0 do sterty
	iota( sterta.begin(), sterta.end(), 0 );
	Sortownik cmp(klastry);

	int pit = 0;
	Zliczenie zliczenie = zliczaj_klastry( klastry ); // TODO - oblicz wartosci poczatkowe!!!!!!!!!!!!!!!!!!!

	// porzadkuje klastry w kolejnosci kolizji, od najmniejszego do najwiekszego
	make_heap( sterta.begin(), sterta.end(), cmp );
	//cerr << "Zastertowana kolejka " << tekst_stertowy( sterta, cmp ) << endl;

	// przetwarzam dopoki sa piekarniki
	while( pit < piekarniki.size() ) {
		//cerr << "@@@@@@ Zaczynam przetwarzanie, piekarnik = " << tekst(piekarniki[pit]) << endl;
		//cerr << "  Pierwszy skoliduje klaster nr " << sterta.front() << "  " << tekst(klastry[sterta.front()]) << endl;
		//cerr << "  (Inne klastry tez moga kolidowac przy tym samym piekarniku)" << endl;

		assert( sterta.size() > 0 );
		assert( pit < piekarniki.size() );

		// Rozpoczynam scalanie (jesli potrzebne)
		{
			//vint do_polaczenia = { 0 }; // hack, zawsze lacz 0
			vint do_polaczenia;
			lolo dekor = piekarniki[pit].czas;
			//cerr << "Sciagam ze sterty kolidujace przy " << dekor << endl;
			//cerr << "Poczatkowy uklad sterty " << tekst_stertowy( sterta, cmp ) << endl;
			
			while( (sterta.size() > 0) && (klastry[sterta.front()].dekor <= dekor ) ) {
				do_polaczenia.push_back( sterta.front() ); 
				pop_heap( sterta.begin(), sterta.end(), cmp ); sterta.pop_back();
				//cerr << "  Uklad sterty " << tekst_stertowy( sterta, cmp ) << " (wyciagnalem " << do_polaczenia.back() << ")" << endl;
			}

			//cerr << "Koncowy uklad sterty " << tekst_stertowy( sterta, cmp ) << endl;
			//cerr << "Do polaczenia: " << tekst(do_polaczenia) << endl;
	
			//cerr << "Klastry przed scaleniem " << tekst(klastry);
			vint scalone = scalaj_klastry( klastry, do_polaczenia, dekor, zliczenie );
			//cerr << "Scalone " << tekst(scalone) << " (kazdy ze scalonych spadl wczesniej ze sterty) " << endl;
			//cerr << "Klastry po scaleniu " << tekst(klastry);

			for( auto s: scalone ) {
				//hack if( s == 0 ) { continue; };
				//cerr << "Wkladam na sterte " << s << " " << tekst(klastry[s]) << endl;
				sterta.push_back( s ); push_heap( sterta.begin(), sterta.end(), cmp );
			}

			//cerr << "Sterta po uzupelnieniu " << tekst_stertowy( sterta, cmp ) << endl;
			//cerr << tekst(klastry);
		}
		// ostatni musi miec decor = MAX zatem nigdy nie zleci ze sterty
		assert( sterta.size() > 0 );
		//cerr << "Zestawienie przed rozpoczeciem zliczania " << tekst(zliczenie) << endl;
		//cerr << "Dekor na poczatku sterty " << klastry[sterta.front()].dekor << endl;

		while( (pit < piekarniki.size()) && (piekarniki[pit].czas < klastry[sterta.front()].dekor) ) {
			lolo pie = piekarniki[pit].czas;
			lolo wynik = pie * zliczenie.nn1 - zliczenie.rabat + klastry[0].krotnosc * klastry[0].piekarnik_przedzerowy(pie);

			assert( wynik >= 0 );
			if( wynik < 0 ) {
				//cerr << "breakpoint" << endl;
			}

			wyniki[ piekarniki[pit].poz ] = wynik;
			//cerr << "ooo Wynik dla piekarnika nr " << pit << tekst(piekarniki[pit]) << " = " << wynik << endl;
			
			++pit;
		}
	}

	return wyniki;
}

#ifndef WDOMU

int main() {
	ios_base::sync_with_stdio( false );

	int ile_klientow; cin >> ile_klientow; // 1 .. 200_000
	int ile_piekarnikow; cin >> ile_piekarnikow; // 1 .. 200_000

	vlolo czasy_przyjscia( ile_klientow );
	for( int i = 0; i < ile_klientow; ++i ) {
		cin >> czasy_przyjscia[i];
	}

	vector< Piekarnik > piekarniki( ile_piekarnikow );
	for( int i = 0; i < ile_piekarnikow; ++i ) {
		cin >> piekarniki[i].czas;
		piekarniki[i].poz = i;
	}
	sort( piekarniki.begin(), piekarniki.end(), [](Piekarnik const&a, Piekarnik const&b) {
		return a.czas < b.czas;
	});

	vlolo opoznienia = oblicz_opoznienia( czasy_przyjscia, piekarniki.front().czas );
	vector< Klaster > klastry = przygotuj_klastry( czasy_przyjscia, opoznienia );

	//cerr << "Klastrow " << klastry.size() << " obliczone dla piekarnika " << tekst(piekarniki.front()) << endl; 
	dekoruj_klastry( klastry );
	//cerr << tekst( klastry );
	vlolo wyniki = rozwiaz( klastry, piekarniki );
	for( auto w: wyniki ) {
		cout << w << "\n";
	}
}

#endif