Ilość podciągów różnowartościowych

Mam problem z tym zadaniem (wrzucam w załączniku, pochodzi z serwisu MAIN2), gdyż daje dobre odpowiedzi, niestety w niektórych testach przekracza minimalnie limity czasowe (w załączniku raport sprawdzania), sugeruje to, że rząd złożoności jest ok, wg mojego oszacowania to O(n^2), ale pewnie robię jakieś rzeczy niepotrzebnie, lub nie uwzględniam informacji o liczbie rodzajów smakołyków, co jest bardzo prawdopodobne, bo bez powodu jej nie podali. Algorytm to taka gąsienica, tylko nie do końca :D jeśli ciąg c[i] c[i+1] ... c[j] jest różnowartościowy to oczywiście ciągów zawierających c[j] jest j-i+1, więc o tyle zwiększamy licznik k, potem sprawdzamy indeks pierwszego wystąpienia c[j+1] w ciągu c[i] c[i+1] ... c[j+1], oczywiście poprzedni ciąg był różnowartościowy, więc w c[i]...c[j] może być co najwyżej jedno wystąpienie, jeśli otrzymamy j+1 oznacza to, że w ciągu c[i]...c[j] nie występuje c[j+1], więc do licznika dodajemy (j+1)-i+1, w przeciwnym razie dla wystąpienia p<j+1, wiemy że c[p+1] ... c[j+1] będzie różnowartościowym ciągiem i licznik zwiększamy o (j+1)-(p+1)+1, dalej będziemy rozpatrywać zakres p+1 do j+2, itd, aż dojdziemy do końca tablicy, mam nadzieje, że bardziej pomogłem w zrozumieniu mojego toku myślenia, niż przeszkodziłem :)

#include<stdio.h>

using namespace std;

int n,m;//n-ilość smakołyków m-ilość dostępnych rodzajów
int c[1000000];//rodzaje kolejnych smakołyków
void g_data(int &n1,int &m1,int tab[])//pobiera dane
{
	scanf("%i%i",&n1,&m1);
	for(int i=0;i<n1;i++)
	{
		scanf("%i",&tab[i]);
	}
}
int srch_f_same(int tab[],int p,int e)//dla tab[e] wyszukuje indeks pierwszego jego wystąpienia w zakresie tab[p]...tab[e]      
{
	int i=p;
	while(i<e+1)
	{
		if(tab[e]==tab[i])
			return i;
		i++;
	}
}
int ciag_max(int &n1,int &m1,int tab[])
{
	int i=0;//indeks początku zakresu
	int k=0;//licznik-odpowiedź na pytanie z zadania
	int i_p=0;
	for(int j=0;j<n1;j++)
	{
		i_p=srch_f_same(tab,i,j);
		if(i_p!=j)
			i=i_p+1;
		k+=(j-i+1);
	}
	return k;
}
int main()
{
	g_data(n,m,c);
	printf("%i",ciag_max(n,m,c));
	return 0;
}

Z uzyciem dodatkowej struktury danych: set. Idea: dla n < 4 policzyc ręcznie, dla n > 3, policzyć ilośc podciągów dla trzech pierwszych wyrazów, dodać je do zbioru, a następnie: iterując od trzeciego, sprawdzać czy element jest równy aktualnemu, czy jest w zbiorze, itd..., te różne przypadki, dają odpowiednie "zinkrementowania n". Złożoność: O(n), pseudokod (Python):

def compute_3(xs):
	if xs[0] != xs[1] and xs[1] != xs[2] and xs[0] != xs[2]:
		return 6
	elif xs[0] == xs[1] and xs[1] != xs[2]: return 4
	elif xs[0] == xs[2] and xs[2] != xs[1]: return 4
	elif xs[1] == xs[2] and xs[2] != xs[0]: return 4
	else: return 3
	

def subseries(xs):
	limit = len(xs)
	
	# edge cases, n = 1, n = 2, n = 3
	if limit == 1: return 1
	if limit == 2:
		if xs[0] == xs[1]: return 2
		else: return 3
	if limit == 3:
		return compute_3(xs)
	
	# n > 3
	n = compute_3(xs) - 3
	s = set() # initialize set
	s.add(xs[0])
	s.add(xs[1])
	s.add(xs[2])
	for i in range(2, limit - 1): # i from 2 to limit - 1 (exclusive)
		if xs[i] != xs[i+1]:
			if xs[i + 1] in s:
				if xs[i + 1] == xs[i - 1] or xs[i] == xs[i - 1]:
					n += 1
				else: 
					n += 2
			else:
				n += 3
			s.add(xs[i + 1])	
	return n + limit

print(subseries([1, 3, 2, 2, 3])) # -> 9
print(subseries([1, 2, 3, 4])) # -> 10 (the all subseries)
print(subseries([1, 2, 2, 2, 2])) # -> 6

Twoje limitu nie są przekroczone tylko troszkę, po prostu chwilę po przekroczeniu czasu Twój program jest zabijany. Skoro n < 1000000, to znaczy że oczekiwane złożoność to n*log(n).