# Suffissi 50/100 fuori tempo

**URL:** <https://forum.olinfo.it/t/suffissi-50-100-fuori-tempo/5889>\
**Category:** Aiuto\
**Created:** [13 Novembre 2019, 9:57pm UTC](https://forum.olinfo.it/t/suffissi-50-100-fuori-tempo/5889 "2019-11-13T21:57:57Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\
**Post date:** [13 Novembre 2019, 9:57pm UTC](https://forum.olinfo.it/t/suffissi-50-100-fuori-tempo/5889/1 "2019-11-13T21:57:57Z")

</div>

Stavo provando a fare il problema: [https://training.olinfo.it/#/task/suffissi/statement](http://Suffissi). 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?

```auto
#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;
}

}

```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [14 Novembre 2019, 4:38pm UTC](https://forum.olinfo.it/t/suffissi-50-100-fuori-tempo/5889/2 "2019-11-14T16:38:04Z")

</div>

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

> [@alep](#):
>
> ```
> for(f=w.begin();f!=w.end();++f){
> l++; 
> }
> 
> ```

ed utilizzare la funzione [size()](http://www.cplusplus.com/reference/set/set/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 🙂