Taulukko

#include <iostream>
#include <map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
long long int tri(long long int n)
{
	return (n * (n + 1)) / 2;
}
 
int main()
{
	int n, k;
	cin >> n >> k;
 
	int *a = new int[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];
 
	vector<pair<int, int>> ranges, overlaps;
	vector<int> ols;
 
	map<int, int> nums;
	nums[a[0]] = 1;
	int u = 1;
 
	for(int i = 0, j = 0; j < n;)
	{
		while(u <= k && j < n - 1)
		{
			j++;
			if(!nums[a[j]])
				u++;
			nums[a[j]]++;
		}
 
		if(u > k)
		{
			nums[a[j]]--;
			u--;
			j--;
		}
 
		//cout << i << ", " << j << endl;
		ranges.push_back(make_pair(i, j));
 
		if(j == n - 1)
			break;
 
		while(u == k && i <= j)
		{
			nums[a[i]]--;
			if(!nums[a[i]])
				u--;
			i++;
		}
	}
 
 
	/*for(int i = 0; i < ranges.size(); i++)
	{
		//cout << "(" << ranges[i].first << ", " << ranges[i].second << "): ";
		for(int j = 1; i + j < ranges.size(); j++)
		{
			if(ranges[i].second < ranges[i+j].first)
				break;
 
			//cout << "(" << ranges[i+j].first << ", " << ranges[i+j].second << "), ";
			//overlaps.push_back(make_pair(ranges[i+j].first, ranges[i].second));
			ols.push_back(ranges[i].second - ranges[i+j].first + 1);
		}
		//cout << endl;
	}*/
 
	//for(pair<int, int> p : ranges)
	//	cout << p.first << ", " << p.second << endl;
 
	//cout << endl;
	//for(int i = 0; i < ols.size(); i++)
	//	cout << overlaps[i].first << ", " << overlaps[i].second << ", " << ols[i] << endl;
 
	long long int ret = 0;
 
	for(pair<int, int> p : ranges)
		ret += tri(p.second - p.first + 1);
 
	for(int i : ols)
		ret -= tri(i);
 
	cout << ret << endl;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 1

Verdict: WRONG ANSWER

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: WRONG ANSWER

Test 11

Group: 1

Verdict: WRONG ANSWER

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: WRONG ANSWER

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: WRONG ANSWER

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: WRONG ANSWER

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 3

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: WRONG ANSWER

Test 34

Group: 3

Verdict: WRONG ANSWER

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: WRONG ANSWER

Test 37

Group: 4

Verdict: ACCEPTED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: ACCEPTED

Test 40

Group: 4

Verdict: ACCEPTED

Test 41

Group: 4

Verdict: WRONG ANSWER

Test 42

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 4

Verdict: WRONG ANSWER

Test 44

Group: 4

Verdict: WRONG ANSWER

Test 45

Group: 4

Verdict: WRONG ANSWER

Test 46

Group: 4

Verdict: ACCEPTED

Test 47

Group: 4

Verdict: ACCEPTED

Test 48

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 49

Group: 4

Verdict: ACCEPTED

Test 50

Group: 4

Verdict: ACCEPTED

Test 51

Group: 4

Verdict: ACCEPTED

Test 52

Group: 4

Verdict: ACCEPTED