# Pausa caffè (caffè) **URL:** \ **Category:** Aiuto\ **Created:** [21 Ottobre 2017, 11:15am UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830 "2017-10-21T11:15:08Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\ **Post date:** [21 Ottobre 2017, 11:15am UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/1 "2017-10-21T11:15:08Z")
Ciao ragazzi, sono riuscito a fare 70/100 nel problema pausa caffè (ois 2016), fallendo nell’ultimo task per esecuzione fuori tempo. La mia soluzione, in effetti, non è molto efficiente. Come tag ho visto che c’è ricerca binaria, ma non capisco come applicarla al problema. Ci sarebbe qualcuno che mi può dare qualche aiutino? Grazie in anticipo. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [21 Ottobre 2017, 12:30pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/2 "2017-10-21T12:30:13Z")
Ciao, non bisogna esattamente utilizzare la ricerca binaria (o almeno io non l’ho utilizzata). Avrai certo notato che gli intervalli sono compresi tra 0 e 10^9, quello che devi fare è utilizzare una struttura dati in grado “compattare” gli intervalli, poi basta solo scorrerli in ordine. ---
**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\ **Post date:** [21 Ottobre 2017, 3:01pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/3 "2017-10-21T15:01:56Z")
In che senso “compattare” ? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [21 Ottobre 2017, 3:13pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/4 "2017-10-21T15:13:24Z")
Un array di dimensione 10^9 direi che occupa un po’ troppa memoria, tuttavia alcune di queste informazione non verranno mai utilizzate poiché N è al più 40000, quello a cui mi riferivo io era una `std::map` dove inserisci solo i valori che leggi in input. ---
**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\ **Post date:** [23 Ottobre 2017, 1:13pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/5 "2017-10-23T13:13:17Z")
Grazie per il tuo aiuto, ma continuo a non capire. A cosa dovrebbe servirmi una map? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [23 Ottobre 2017, 3:40pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/6 "2017-10-23T15:40:06Z")
In effetti mi sono accorto solo ora che gli intervalli sono compresi tra 0 e 10^6 e non 10^9 e quindi si poteva evitare di usare la map, comunque il ragionamento è uguale usando o no la map. Quello che interessa a noi è sapere all’istante t quante persone ci sono al caffè, per farlo utilizziamo una array o una map dove alla posizione i mettiamo un 1 se arriva una persona e un -1 se se ne va una persona, in questo modo scorrendo possiamo sapere quante persone ci sono in ogni istante. ---
**Author:** ![Keyword](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ebca7d/32.png) [@Keyword](https://forum.olinfo.it/u/Keyword)\ **Post date:** [23 Ottobre 2017, 5:11pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/7 "2017-10-23T17:11:48Z")
Mi hai fatto venire in mente un fenwick… che ne pensi? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [23 Ottobre 2017, 6:15pm UTC](https://forum.olinfo.it/t/pausa-caffe-caffe/4830/8 "2017-10-23T18:15:56Z")
Generalmente in questo tipo di problemi abbiamo tre possibili soluzioni: - Brute force: update O(N), query O(1) - Lazy: update O(1), query O(N) - Fenwick: update O(logN), query O(logN) In questo problema abbiamo N update all’inizio e un’unica query alla fine e non vedo il senso di usare un fenwick.