# Sfere Numerate - Time Limit - Tai

**URL:** <https://forum.olinfo.it/t/sfere-numerate-time-limit-tai/6317>\
**Category:** Aiuto\
**Created:** [15 Ottobre 2020, 3:02pm UTC](https://forum.olinfo.it/t/sfere-numerate-time-limit-tai/6317 "2020-10-15T15:02:53Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![CristianCinieri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/c/977dab/32.png) [@CristianCinieri](https://forum.olinfo.it/u/CristianCinieri)\
**Post date:** [15 Ottobre 2020, 3:02pm UTC](https://forum.olinfo.it/t/sfere-numerate-time-limit-tai/6317/1 "2020-10-15T15:02:53Z")

</div>

Sto cercando di risolvere il problema [sfere numerate (tai)](https://training.olinfo.it/#/task/tai_sfere/statement). Non riesco ad essere nel time limit. I test case che ho provato in locale e quelli che escono sulla piattaforma sono corretti. Qualche consiglio/suggerimento per ridurre il tempo?

> ```
> #include<bits/stdc++.h>
> using namespace std;
> 
> vector<int> sphere;
> void inizio(int N,int M, int sfere[]){
> for (int i = 0; i < N; i++)
> sphere.push_back(sfere[i]);
> }
> void modifica(int posizione,int valore){
> sphere[posizione] = valore;
> }
> bool verifica(int l,int r){
> set<int> v;
> int K = (r - l) + 1;
> 	
> for(int i = 0; i < K; i++) v.insert(sphere[l + i]);
> 
> set<int>::iterator lastIt = v.end();
> lastIt--;
> if(*lastIt == K && v.size() == K) 
> return true; 
> else 
> return false;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![Doxeno](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doxeno/32/648_2.png) [@Doxeno](https://forum.olinfo.it/u/Doxeno)\
**Post date:** [15 Ottobre 2020, 3:40pm UTC](https://forum.olinfo.it/t/sfere-numerate-time-limit-tai/6317/2 "2020-10-15T15:40:44Z")

</div>

La complessità della tua soluzione è O(NMlogN), che per N\leq100000 è un numero decisamente grande (Si possono fare circa 10^8 operazioni al secondo).  
Per arrivare a fare 100 devi usare una struttura dati che supporti point updates e range queries, oltre a trovare delle condizioni abbastanza belle per verificare che in quel range ci siano esattamente quegli elementi.