fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vi = vector<int>;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t; 
  10.     cin >> t;
  11.     while (t--) {
  12.         int n;
  13.         cin >> n;
  14.         vector<int>a(n);
  15.         for (int i = 0; i < n; i++) {
  16.             cin >> a[i];
  17.         }
  18.  
  19.         // 1) Build, for each value v, the sorted list of all positions where v appears
  20.         //    so that we can find "the first occurrence > x" by binary search.
  21.         vector<vi> pos(n+1);
  22.         for (int i = 0; i < n; i++) {
  23.             pos[a[i]].push_back(i);
  24.         }
  25.  
  26.         int ans = 0;
  27.         int start = 0;
  28.         // We'll keep the distinct‐set of the *previous* segment here:
  29.         unordered_set<int> prevDistinct;
  30.  
  31.         while (start < n) {
  32.             // If prevDistinct is empty, we can start our new segment with length = 1
  33.             int end;
  34.             if (prevDistinct.empty()) {
  35.                 end = start;
  36.             }
  37.             else {
  38.                 // Otherwise, we must stretch this segment until *every* v in prevDistinct
  39.                 // has appeared at least once in [start..end].
  40.                 // We'll keep a count of which of those we've already seen.
  41.                 unordered_set<int> covered;
  42.                 end = start;
  43.                 bool ok = true;
  44.                 while (true) {
  45.                     if (end >= n) {
  46.                         // we ran off the end without covering prevDistinct:
  47.                         ok = false;
  48.                         break;
  49.                     }
  50.                     int v = a[end];
  51.                     if (prevDistinct.count(v)) 
  52.                         covered.insert(v);
  53.                     if (covered.size() == prevDistinct.size())
  54.                         break;
  55.                     end++;
  56.                 }
  57.                 if (!ok) {
  58.                     // impossible to build a successor segment that inherits all of prevDistinct
  59.                     // so we *merge* everything from `start`..`n-1` into the *last* segment and stop
  60.                     break;
  61.                 }
  62.             }
  63.  
  64.             // [start..end] is our next segment
  65.             ans++;
  66.  
  67.             // build its distinct‐set to pass to the following round
  68.             unordered_set<int> currDistinct;
  69.             for (int i = start; i <= end; i++) 
  70.                 currDistinct.insert(a[i]);
  71.  
  72.             prevDistinct = move(currDistinct);
  73.             start = end + 1;
  74.         }
  75.  
  76.         // If we exited the loop with start < n, that remainder (from start to n-1)
  77.         // needs to be merged into the *last* segment we already counted, so we do *not*
  78.         // increment `ans` again.  If we exactly consumed to the end, we're done.
  79.  
  80.         // Edge‐case: if we never counted any segment (which only happens if n=0) we’d need one—
  81.         // but the constraints guarantee n≥1, so ans≥1 by construction.
  82.  
  83.         cout << ans << "\n";
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
8
6
1 2 2 3 1 5
8
1 2 1 3 2 1 3 2
5
5 4 3 2 1
10
5 8 7 5 8 5 7 8 10 9
3
1 2 2
9
3 3 1 4 3 2 4 1 2
6
4 5 4 5 6 4
8
1 2 1 2 1 2 1 2
stdout
copy 
2
3
1
3
1
3
3
4
https://ideone.com/kEDDDB
language:
C++ (gcc 8.3)
created:
5 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!