Sfere Numerate - Time Limit - Tai

Sto cercando di risolvere il problema sfere numerate (tai). 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;
}

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.

1 Mi Piace