fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int count(int k , vector<int>& arr){
  7. 	int i=0;
  8. 	int j=0;
  9. 	unordered_map<int,int> mpp;
  10. 	int ans=0;
  11. 	int n = arr.size();
  12.  
  13.  
  14. 	while(j<n){
  15. 		mpp[arr[j]]++;
  16. 		while(mpp.size()>k){
  17. 			mpp[arr[i]]--;
  18. 			if(mpp[arr[i]]==0){
  19. 				mpp.erase(arr[i]);
  20. 			}
  21. 			i++;
  22. 		}
  23. 		ans+=(j-i+1);
  24. 	    j++;
  25.  
  26. 	}
  27. 	return ans;
  28.  
  29. }
  30.  
  31.  
  32. int main() {
  33. 	// your code goes here
  34. 	int n;
  35. 	cin>>n;
  36. 	vector<int> arr(n);
  37.  
  38. 	for(int i=0;i<n;i++){
  39. 		cin>>arr[i];
  40. 	}
  41.  
  42. 	int tot = n*(n+1)/2;
  43. 	int v=0;
  44.  
  45. 	if(tot%2==0){
  46. 		v=tot/2;
  47. 	}
  48. 	else{
  49. 		v=(tot+1)/2;
  50. 	}
  51.  
  52. 	int low=1;
  53. 	int high = n;
  54. 	int ans=0;
  55.  
  56. 	while(low<=high){
  57. 		int mid = (low+high)/2;
  58.  
  59. 		if(count(mid,arr)>=v){
  60.              ans=mid;
  61.              high=mid-1;
  62.  
  63. 		}
  64. 		else{
  65. 			low = mid+1;
  66. 		}
  67. 	}
  68.  
  69. 	cout<<ans<<endl;
  70.  
  71.  
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
5  
5 5 2 2 1
stdout
copy 
2
https://ideone.com/SamPWz
language:
C++14 (gcc 8.3)
created:
1 day 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!