Aiuto con Soste in Autostrada (autogrill) (Execution timed out)

Aiuto
1

Salve a tutti, stavo provando a risolvere Soste in Autostrada (autogrill) ed ero arrivato a questo codice che risolve in tempo solo gli esempi e i testcase 018 e 020, andando in Execution timed out in tutti gli altri.

#include <set>

using namespace std;

set<long long> autogrillAperti;

void inizia() {
  return;
}

void apri(long long p) {
  autogrillAperti.insert(p);
}

void chiudi(long long p) {
  autogrillAperti.erase(p);
}

long long chiedi(long long p) {
  if (autogrillAperti.size()==0){
    return -1;
  }else{
    set<long long>::iterator iteratore=lower_bound(autogrillAperti.begin(), autogrillAperti.end(), p);
    if(*iteratore==p || iteratore==autogrillAperti.begin()){
      return *iteratore;
    }else if(iteratore==autogrillAperti.end()){
      iteratore--;
      return *iteratore;
    }else{
      long long avanti=*iteratore;
      iteratore--;
      if(p-*iteratore<avanti-p){
        return *iteratore;
      }else{
        return avanti;
      }
    }
  }
}

Dopo aver provato ad ottimizzarlo senza troppo successo sono andato sui forum dove ho trovato degli altri argomenti come ad esempio questo dove il codice è molto simile al mio ma non sembra avere dei problemi di tempo limite, qualcuno saprebbe spiegarmi cosa rallenta tanto il mio codice?
Grazie mille

2

Ho provato a sottoporre varie versioni del codice cambiando qualcosa qua e là e ho scoperto che il problema stava nel fatto che usavo

lower_bound(autogrillAperti.begin(), autogrillAperti.end(), p)

invece di

autogrillAperti.lower_bound(p)

che a quanto pare è molto più veloce dato che adesso tutti i testcase sono abbondantemente (0.6 s) sotto al secondo.
Mi pareva di aver capito avessero entrambi una complessità di O(log(N)) ma avrò capito male.

3

La funzione è generica per tutti gli iteratori. Siccome gli iteratori dei set non supportano random access devono essere incrementati un passo alla volta. Per questo la funzione è \mathcal O (N)
Il metodo specifico dei set invece è \mathcal O (\log N)

2 Mi Piace