jakaria_hossain

codeforce - longest k-good segment

Jul 20th, 2019
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. map<int,int>mp;
  4. int cnt=0;
  5.  
  6. void del(int x)
  7. {
  8. mp[x]--;
  9. if(mp[x]==0)
  10. cnt--;
  11. }
  12. void add(int x)
  13. {
  14. mp[x]++;
  15. if(mp[x]==1)
  16. cnt++;
  17. }
  18.  
  19. int main()
  20. {
  21. int n,k;
  22. cin>>n>>k;
  23. int ara[n+1],i,j,cmp=0,l,r;
  24. for(i=0; i<n; i++)
  25. cin>>ara[i];
  26. i=0;
  27. j=0;
  28. cnt=0;
  29.  
  30. while(j<n)
  31. {
  32. if(cnt<=k)
  33. {
  34. add(ara[j]);
  35. }
  36.  
  37. if(cnt>k)
  38. {
  39.  
  40. del(ara[i]);
  41. i++;
  42.  
  43. }
  44. if(cnt<=k)
  45. {
  46. if(cmp<=j-i)
  47. {
  48. cmp=j-i;
  49. l=i+1;
  50. r=j+1;
  51. }
  52. j++;
  53. }
  54. }
  55.  
  56. cout<<l<< " "<<r<<endl;
  57. }
RAW Paste Data