Suffissi 50/100 fuori tempo

Aiuto
1

Stavo provando a fare il problema: https://training.olinfo.it/#/task/suffissi/statement. Sono riuscito a “risolverlo” solo che il task 4 e 5 vanno in Execution timed out. Non riesco a trovare il modo di accorcialo, qualche consiglio?

#include <bits/stdc++.h>
using namespace std;

int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin.tie(0);
cin.sync_with_stdio(0);

set <long long> w;
set <long long>::iterator f;

int N,M,l=0;
cin>>N;
cin>>M;
long long a[N],b;
for(int i=1;i<=N;i++){
	cin>>a[i];
}
for(int i=1;i<=M;i++){
	w.clear();
	l=0;
	cin>>b;
		for(int kk=b;kk<=N;kk++){
			w.insert(a[kk]);
		}
		for(f=w.begin();f!=w.end();++f){
			l++;
		}
	
	cout<<l<<endl;
}


}
1 Mi Piace
2

Salve!
Il tuo programma, per quanto corretto, ha una complessità troppo alta, infatti il numero di operazioni è circa uguale a 10^{10}(n\cdot m).
Innanzi tutto suggerisco di evitare cicli inutili come

ed utilizzare la funzione size().
Per ottimizzare ulteriormente il programma basta un semplice trucco:

Non c’è bisogno di scorrersi ogni volta l’array per ogni b_i in input, cerca un modo per precalcolarti efficientemente tutte le risposte possibili dopo aver letto gli a_i

Spero di essere stato d’aiuto :slightly_smiling_face:

2 Mi Piace