fork download
copy 
  1. #include<iostream>
  2. #include<set>
  3. #include<map>
  4. #include<vector>
  5. using namespace std;
  6.  
  7. int main() {
  8. 	int n, x;
  9. 	cin >> n >> x;
  10.  
  11. 	vector<int> a(n);
  12. 	for(int i = 0; i < n; i++) cin >> a[i];
  13.  
  14. 	int end = 0;
  15. 	long long ans = 0;
  16.  
  17. 	set<int> uniq;
  18. 	map<int, int> freq;
  19. 	for(int start = 0; start < n; start++) {
  20. 		while(uniq.size() <= x && end < n) {
  21. 			if(uniq.size() == x && freq[a[end]] == 0) {
  22. 				break;
  23. 			}
  24. 			uniq.insert(a[end]);
  25. 			freq[a[end]]++;
  26. 			end++;
  27. 		}
  28. 		ans += end - start;
  29. 		freq[a[start]]--;
  30. 		if(freq[a[start]] == 0) {
  31. 			uniq.erase(a[start]);
  32. 		}
  33. 	}
  34. 	cout << ans;
  35. }
  36.  
Success #stdin #stdout 0s 15240KB
comments ()
stdin
copy 
5 2
1 2 3 1 1
stdout
copy 
10
https://ideone.com/v2CdZO
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!