Soste in autostrada (autogrill) help

Aiuto
1

Salve a tutti, è da oggi che provo a risolvere il problema, conosco poco la struttura dei set e map e il funzionamento degli iteratori pero mi sono letto un po’ della reference e sono riuscito a risolvere i casi di esempio. Tutti gli altri testcase però mi danno Execution timed out e uno output non corretto.

#include<bits/stdc++.h>

using namespace std;
set<long long> s;

void inizia(){

}

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

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

long long chiedi(long long p){
	if(s.size() == 0)
		return -1;
	set<long long>::iterator it_prec; 
	set<long long>::iterator it_succ; 
	auto it = lower_bound(s.begin(), s.end(), p); //primo autogrill in/dopo p
	if(it != s.begin()){
		it_prec = prev(it);
											//cout<<*prev(it)<<endl;
    	if ((*it - p) > (p - *it_prec))
        	return *it_prec;
		else
			return *it;
		}
	else
		return *it;

}

Ho visto anche i post simili ma se provo ad analizzare quei codici mi vengono mille altri dubbi quindi vorrei cercare di sistemare il mio che almeno ho fatto in modo che riesca risolvere i casi di esempio.
Ringrazio chiunque possa aiutarmi :blush:

2

Praticamente gli iteratori di un set non sono random access quindi per spostarti da un iteratore all’altro devi passare per tutti quelli di mezzo, il che rende lower_bound() alla meglio \mathcal{O}(N). Appunto perché esiste questo problema i set implementano il metodo .lower_bound() che fa esattamente la stessa cosa della funzione ma in \mathcal{O}(\log N).
In quanto alle WA, quelle sono dovute al fatto che non stai controllando che l’iteratore restituito da lower_bound non sia s.end()

3

Grazie mille ho fatto una mega confusione con questi lower_bound (certo che potevano fare nomi diversi per i due iteratori ho dovuto leggere 5 volte per capire la tua risposta :joy:)