fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. typedef long long ll;
  5.  
  6. const int MAXN = 3e5+5;
  7.  
  8. int N, K, A[2*MAXN], last[MAXN];
  9.  
  10. signed main () {
  11.   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12.   cin >> N >> K;
  13.   int ans = K-1;
  14.   for(int i=1; i<=N; i++){
  15.       cin >> A[i];
  16.       A[i+N] = A[i];
  17.   }
  18.   set<int> st;
  19.   st.insert(A[1]);
  20.   last[A[1]] = 1; 
  21.   for(int i=1, j=1; i<=N; ){ // [i,j]
  22.     if(*st.rbegin() - *st.begin() >= K){
  23.         st.erase(A[i]);
  24.         i++;
  25.     }else{
  26.         ans = min(ans, K-(int)st.size());
  27.         j++;
  28.         if(st.count(A[j])) {
  29.             while(i <= last[A[j]]){
  30.                 st.erase(A[i]);
  31.                 i++;
  32.             }
  33.         }
  34.         last[A[j]] = j;
  35.         st.insert(A[j]);             
  36.     }    
  37.   }
  38.   cout << ans;
  39. }
Success #stdin #stdout 0s 5648KB
comments (?)
stdin
copy 
10 4
1 7 8 4 5 1 7 8 2 4
stdout
copy 
1
https://ideone.com/zkEXCZ
language:
C++ (gcc 8.3)
created:
4 days 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!