fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5 + 11;
  6.  
  7. int n, k, a[MAXN];
  8. long long res = 0;
  9.  
  10. int main()
  11. {
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(NULL);
  14.     cin >> n >> k;
  15.  
  16.     for (int i = 1; i <= n; ++i)
  17.     {
  18.         cin >> a[i];
  19.     }
  20.  
  21.     int left = 1;
  22.     unordered_map<int, int> mp;
  23.     for (int right = 1; right <= n; ++right)
  24.     {
  25.         ++mp[a[right]];
  26.         while (mp.size() > k)
  27.         {
  28.             if (mp[a[left]] == 1)
  29.             {
  30.                 mp.erase(a[left]);
  31.             }
  32.             else
  33.             {
  34.                 --mp[a[left]];
  35.             }
  36.             ++left;
  37.         }
  38.         res += right - left + 1;
  39.     }
  40.  
  41.     printf("%lld", res);
  42.  
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 5464KB
comments (?)
stdin 
7 3
2 6 4 3 6 8 3
stdout 
20
https://ideone.com/znTk3B
language:
C++14 (gcc 8.3)
created:
2 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!