Police 7 52/100

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 :scream:.
Secondo me c’è un metodo più veloce per computare questa somma, ma purtroppo non mi viene in mente nulla :pensive:
Qualcuno mi può guidare verso la strada giusta?

Non ho usato un segment tree, quindi non so se quello che segue ti può tornare utile, ma ho gestito a parte le modifiche solo sull’ultimo elemento:
Per gli altri subtask ho usato un map<int,int>massimi poi ho gestito i quattro casi possibili:

  1. il valore cresce e non è uno dei massimi che c’erano già, se supera il massimo successivo guardo a sinistra altrimenti …

  2. il valore cresce ed è uno dei massimi che c’erano già, lo modifico e guardo a sinistra…

  3. il valore decresce e non è uno dei massimi che c’erano già non faccio niente

  4. il valore decresce ed era uno dei massimi riguardo le cose dal massimo precedente fino a questo …

E’ venuto fuori un codice molto ma molto lungo ma veloce.