fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long 
  3. using namespace std;
  4.  
  5. #define mod 1000000007LL
  6.  
  7.     struct Cell{
  8.     int r,c;
  9.     bool operator<(const Cell& other) const{
  10.         if(r!=other.r)return r<other.r;
  11.         return c<other.c;
  12.     }
  13. };
  14.  
  15. class dsu{
  16.     vector<int>parent,rank;
  17.  
  18. private:
  19.     dsu(int n){
  20.         parent.resize(n);
  21.         rank.resize(n);
  22.  
  23.         for(int i=0;i<n;i++){
  24.             parent[i]=i;
  25.             rank[i]=1;
  26.         }
  27.     }
  28.  
  29.     int find(int i){
  30.         return parent[i]==i ? i : (parent[i]=find(parent[i]));
  31.     }
  32.  
  33.     void unite(int x,int y){
  34.         int s1=parent[x];
  35.         int s2=parent[y];
  36.         if(s1!=s2){
  37.             if(rank[s1]<rank[s2])parent[s1]=s2;
  38.             else if(rank[s2]>rank[s1])parent[s2]=s1;
  39.             else parent[s2]=s1, rank[s1]++;
  40.         }
  41.     }
  42. };
  43.  
  44.  
  45. // bool comparator(vector<int>&a , vector<int>&b){
  46. //     return a[2]<b[2];
  47. // }
  48.  
  49. // bool comparator(pair<pair<int,int>,int> &a, pair<pair<int,int>,int> &b ){
  50. //     return a.second > b.second;
  51. // }
  52.  
  53. int t;
  54. int cnt=0;
  55. bool check=false;
  56.  
  57. int fact(int n){
  58.     int ans=1;
  59.     for(int i=1;i<=n;i++){
  60.         ans=(ans*i)%mod;
  61.     }
  62.     return ans;
  63. }
  64.  
  65. vector<int> factors(int n){
  66.     vector<int> v;
  67.     for(int i=2;i<n;i++){
  68.         if(n%i==0)v.push_back(i);
  69.     }
  70.     return v;
  71. }
  72.  
  73. bool is_prime(int n){
  74.     if(n==2 || n==3)return true;
  75.     for(int i=2;i*i<=n;i++){
  76.         if(n%i==0)return false;
  77.     }
  78.     return true;
  79. }
  80.  
  81. void solve() {
  82.     int n;
  83.     cin>>n;
  84.     int k;
  85.     cin>>k;
  86.     vector<int>v(n);
  87.     for(int i=0;i<n;i++)cin>>v[i];
  88.     // cout<<n<<" n "<<" k ";
  89.     // to count number of subarray whose count of distinct number <=k
  90.     int ans=0;
  91.     unordered_map<int,int>mp;
  92.     for(int i=0,j=0;j<n;j++){
  93.         mp[v[j]]=mp[v[j]]+1;
  94.         int d=mp.size();
  95.         while(d>k){
  96.             mp[v[j]]=mp[v[j]]-1;
  97.             if(mp[v[j]]==0){
  98.                 mp.erase(v[j]);
  99.             }
  100.             i++;
  101.             d=mp.size();
  102.         }
  103.         ans+=(j-i+1);
  104.     }
  105.     cout<<ans<<endl;
  106. }
  107.  
  108. int32_t main() {
  109.     ios::sync_with_stdio(false);
  110.     cin.tie(0);
  111.     cin>>t;
  112.     // int t=1;
  113.     while(t--){
  114.         cnt++;
  115.         // cout<<"count value : "<<cnt<<endl;
  116.         solve();
  117.     }
  118. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
3 2 
1 2 3
stdout
copy 
5
https://ideone.com/FiuCpR
language:
C++14 (clang 8.0)
created:
18 hours 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!