Advertisement
newb_ie

smallest range that contain k distinct element

Sep 6th, 2020
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. /*
  2. ======================
  3. [     ___T_          ]
  4. [    | 6=6 | =>HI :-)]
  5. [    |__o__|         ]
  6. [ >===]__o[===<      ]
  7. [     [o__]          ]
  8. [      .".           ]
  9. [      |_|           ]
  10. [                    ]
  11. ======================
  12.  */
  13.  
  14. #include<bits/stdc++.h>
  15. using namespace std;
  16. using lli = int64_t;
  17. int main() {
  18.      ios::sync_with_stdio(false);
  19.      cin.tie(nullptr);
  20.      cout.tie(nullptr);
  21.      int T = 1;
  22.      for(int t = 1; t <= T; t++) {
  23.          int n,k;
  24.          cin >> n >> k;
  25.          int input[n + 1];
  26.          for(int i = 1; i <= n; i++){
  27.              cin >> input[i];
  28.          }
  29.          map<int,int> count;
  30.          set<int> distincts;
  31.          int l = 1;
  32.          int range_l = 1,range_r = n;
  33.          for(int i = 1; i <= n; i++){
  34.              count[input[i]] += 1;
  35.              distincts.insert(input[i]);
  36.              if((int) distincts.size() >= k){
  37.                  if(range_r - range_l > i - l){
  38.                      range_l = l,range_r = i;
  39.                  }
  40.              }
  41.              while((int) distincts.size() == k){
  42.                  if(count[input[l]] > 1){
  43.                      count[input[l]] -= 1;
  44.                  }else{
  45.                      count[input[l]] = 0;
  46.                      distincts.erase(input[l]);
  47.                  }
  48.                  l += 1;
  49.                  if((int) distincts.size() >= k){
  50.                      if(range_r - range_l > i - l){
  51.                          range_l = l,range_r = i;
  52.                      }
  53.                  }
  54.              }
  55.              if((int) distincts.size() >= k){
  56.                  if(range_r - range_l > i - l){
  57.                      range_l = l,range_r = i;
  58.                  }
  59.              }
  60.          }
  61.          cout << range_l << " " << range_r << "\n";
  62.      }
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement