Advertisement
OIQ

Untitled

OIQ
Nov 26th, 2019
157
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.  
  10.     int t;
  11.     cin >> t;
  12.  
  13.     vector <int> vec(1000001, 0);
  14.     vector <int> a(200001);
  15.  
  16.     for (int dd = 0; dd < t; dd++) {
  17.         int n, k, d;
  18.  
  19.         cin >> n >> k >> d;
  20.  
  21.         for (int i = 0; i < 200001; i++)
  22.             vec[i] = 0;
  23.  
  24.         for (int i = 0; i < n; i++)
  25.             cin >> a[i];
  26.  
  27.         int diff = 0;
  28.         int ans = 2000001;
  29.         for (int i = 0; i < n; i++) {
  30.             if (i < d) {
  31.                 if (vec[a[i]] > 0)
  32.                     vec[a[i]]++;
  33.                 else {
  34.                     vec[a[i]]++;
  35.                     diff++;
  36.                 }
  37.  
  38.             }
  39.  
  40.             else {
  41.                 vec[a[i - d]]--;
  42.                 if (vec[a[i - d]] == 0)
  43.                     diff--;
  44.                 if (vec[a[i]] > 0)
  45.                     vec[a[i]]++;
  46.                 else {
  47.                     vec[a[i]]++;
  48.                     diff++;
  49.                 }
  50.  
  51.                 ans = min(ans, diff);
  52.             }
  53.         }
  54.  
  55.         ans = min(ans, diff);
  56.  
  57.         cout << ans << endl;
  58.  
  59.        
  60.     }
  61.  
  62.  
  63.     return 0;
  64. }
Advertisement
RAW Paste Data Copied
Advertisement