Salve, è da circa 3 giorni che provo a risolvere il problema della classifica senza fili, ma come mi sembra giusto che sia, in 4 dei 7 subtask del testcase va in time out.
Ciò che presumo dia questo problema del timeout è la funzione di squalifica che ha una complessità di O(2N) nel caso peggiore dato che svolge prima una ricerca lineare per eliminare il partecipante dalla classifica, e poi effettua l’eliminazione tramite l’erase e quindi un’altra ricerca lineare.
So che ancora è un problema uscito da pochi giorni sulla piattaforma e che in pochi l’hanno risolto, ma sto davvero impazzendo sul come risolverlo. (Attualmente sono a 34/100)
La soluzione ottimale penso che richieda l’utilizzo di un range tree, così da eseguire in O(logN) la funzione squalifica
L’altra soluzione proposta da @VashTheStampede credo sia la square root decomposition, più semplice e ti fa comunque ottenere qualche punto in più di 34
Un altro metodo carino e semplice da implementare (sebbene leggermente più lento del range tree, nella sua implementazione più banale) è l’utilizzo di un albero di Fenwick per memorizzare gli squalificati precedenti una data posizione
