Tle on SPOJ Audition even with O(n) complexity

Getting tle on spoj Audition.Here is my submission link, Pls help.

Here is the heart of the code:

        map <ll,ll> mp;
		mp.clear();
		mp[0]++;
		ll sum=0,n,k,ans=0;
		cin>>n>>k;
		ll a[n];
		string str;
		cin>>str;
		for(ll i=0;i<n;i++)
		{
			a[i] = str[i] - (ll)'a' + 49;
			sum +=a[i];
			ans +=mp[sum-k];
			mp[sum]++;
		}

time complexity of your code is O(nlog(n)),n is because of for loop and log is because of map.map takes logn time for every operation.

1 Like