Spoj Problem ACMCEG2C - Pick the candies (C++)

  The problem link may be found here.

      Explanation:

• Use Deque to keep track of elements of the variety of candies.
• If i is greater that allowed variety of Candies pop the front element of the queue
• Based of condition only keep the maximum element, pop everything thats smaller than the ith element

 1  #include<bits/stdc++.h>

 2  using namespace std;

 3  void sliding(vector<int>&v,int k){

 4  deque<int>q;

 5  vector<int>res;

 6  for(int i=0;i<v.size();i++){

 7      while(!q.empty() && i-q.front()>=k){

 8          q.pop_front();

 9      }

10      while(!q.empty() && v[q.back()]< v[i]){

11          q.pop_back();

12      }

13      q.push_back(i);

14      if(i>=k-1)res.push_back(v[q.front()]);

15  }

16  for(int i=0;i<res.size();i++){

17          cout<<res[i]<<" ";

18      }

19  }

20  int main(){

21  int t,n,k,m;

22 

23  scanf("%d",&t);

24  while(t--){

25      cin>>n>>k;

26       vector<int>v;

27       vector<int>ans;

28      for(int i=0;i<n;i++){

29          cin>>m;

30          v.push_back(m);

31      }

32      sliding(v,k);

33 

34  cout<<endl;

35  }

36 

37 

38  return 0;}