fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(0);
  6.     cin.tie(0);
  7.  
  8.     int T;
  9.     cin >> T;
  10.     while (T--) {
  11.         int n;
  12.         cin >> n;
  13.  
  14.         vector<int> a(n);
  15.         map<int, vector<int>> p;
  16.         for (int i = 0; i < n; i++) {
  17.             cin >> a[i];
  18.             p[a[i]].push_back(i);
  19.         }
  20.  
  21.         int ans = 0;
  22.         set<int> ts;
  23.         for (int i = 0; i < n - 1; i++) {
  24.             if (a[i] > a[i + 1])
  25.                 ts.insert(i);
  26.         }
  27.  
  28.         while (!ts.empty()) {
  29.             int i = *ts.begin();
  30.             int x = (a[i] > 0) ? a[i] : a[i + 1];
  31.  
  32.             for (int j : p[x]) {
  33.                 a[j] = 0;
  34.                 ts.erase(j - 1);
  35.                 ts.erase(j);
  36.                 if (j > 0 && a[j - 1] > a[j])
  37.                     ts.insert(j - 1);
  38.                 if (j + 1 < n && a[j] > a[j + 1])
  39.                     ts.insert(j);
  40.             }
  41.             ans++;
  42.         }
  43.  
  44.         cout << ans << "\n";
  45.     }
  46.  
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
stdout
copy 
1
2
4
3
0
https://ideone.com/hjJgws
language:
C++ (gcc 8.3)
created:
39 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!