fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. // Function to count subarrays with at most `k` distinct elements
  6. ll count(ll arr[], int n, int k) {
  7.     ll i = 0, j = 0, count = 0;
  8.     unordered_map<ll, ll> freq;
  9.  
  10.     while (j < n) {
  11.         freq[arr[j]]++;
  12.  
  13.         while (freq.size() > k) {
  14.             freq[arr[i]]--;
  15.             if (freq[arr[i]] == 0) {
  16.                 freq.erase(arr[i]);
  17.             }
  18.             i++;
  19.         }
  20.  
  21.         count += (j - i + 1);
  22.         j++;
  23.     }
  24.  
  25.     return count;
  26. }
  27.  
  28. int main() {
  29.     ll n;
  30.     cin >> n;
  31.     ll b[n];
  32.  
  33.     for (ll i = 0; i < n; i++) cin >> b[i];
  34.  
  35.     ll tot = n * (n + 1) / 2; // Total number of subarrays
  36.     ll v = ceil(tot / 2.0); // Half of total subarrays, rounded up
  37.  
  38.     ll left = 1, right = n, r = n;
  39.     while (left <= right) {
  40.         ll mid = (left + right) / 2;
  41.         if (count(b, n, mid) >= v) {
  42.             r = mid;
  43.             right = mid - 1;
  44.         } else {
  45.             left = mid + 1;
  46.         }
  47.     }
  48.  
  49.     cout << r << endl;
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5  
5 5 2 2 1
stdout
copy 
2
https://ideone.com/ZNStYe
language:
C++14 (gcc 8.3)
created:
12 hours 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!