So I was solving this problem and I got every test case right except the one with all ones (test case 5). It was because of time limit exceeded. This is confusing because when I test a smaller test case like
8 8
1 1 1 1 1 1 1 1
I get 36 which is the correct answer. Also, this is \mathcal{O}(n\log{}n) so it should pass the bounds. I also made sure to check for integer overflow and things like that. I was wondering if anybody could tell me why there is a mistake in a corner case like this. Thanks!
My solution
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5+6;
int n,K;
long long arr[mxn],ans=1;
multiset<long long> window1; //Keeps tracks of elements in the window
set<long long> window2; //Keeps track of how many distinct values
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> K;
for(int i=1;i<=n;i++)
cin >> arr[i];
window1.insert(arr[1]),window2.insert(arr[1]);
/* cout << "hi\n"; */
for(int ll=1,rr=1;ll<=n&&rr<n;){ // 2 pointers
if(window1.count(arr[rr+1])||window2.size()<K) // If we can insert another number, increase the right pointer and insert the number
window1.insert(arr[++rr]),window2.insert(arr[rr]),ans+=(rr-ll+1);
else{ //increment the left pointer until we can (the for loop will keep hitting this point)
window1.erase(window1.find(arr[ll++]));
if(!window1.count(arr[ll-1]))
window2.erase(arr[ll-1]);
}
/* cout << "hi\n"; */
/* cout << ans << "\n"; */
}
cout << ans;
}