Oggi, provando ad imparare come utilizzare un segment tree, ho deciso di cimentarmi nella risoluzione del problema Police Investigation 7.
Purtroppo non riesco a fare punteggio pieno perchè la mia soluzione va in TLE. Ho creato un segment tree in cui mi tengo i valori massimi, e ogni volta che arriva una query, aggiorno il valore in quell’indice. Poi procedo a trovare il massimo, tenendomi il valore massimo e l’indice del massimo (che chiamerò lastIndex), ripeto la query con l’indice sinistro lastIndex + 1 e il destro N, continuo così fino a quando lastIndex >= N. Poi stampo la somma dei massimi trovati.
Per intenderci, questo è lo snippet di codice in questione.
update(p, s);
int leftIndex = 0;
long long sum = 0;
while (leftIndex < N) {
pair<long long, int> yes = getMax(1, 0, n, leftIndex, N);
leftIndex = yes.second + 1;
sum += yes.first;
}
cout << sum << endl;
Alla peggio, per calcolare la somma, il mio codice impiega N log N tempo, e moltiplicato per il numero di query il tempo di esecuzione del mio programma diventa QN log N .
Secondo me c’è un metodo più veloce per computare questa somma, ma purtroppo non mi viene in mente nulla …
Qualcuno mi può guidare verso la strada giusta?