fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 2e5+5;
  11.  
  12. int n, a[maxN], truoc[maxN], sau[maxN], truoc_a[maxN], sau_a[maxN];
  13.  
  14. struct custom_set
  15. {
  16.     bool operator()(int a1, int a2) const
  17.     {
  18.         return max(truoc[a1], sau[a1]) < max(truoc[a2], sau[a2]);
  19.     }
  20. };
  21.  
  22. void solve()
  23. {
  24.     int ans = 0;
  25.     set<int, custom_set>clone;
  26.     deque<pair<int,int>>dq;
  27.     for(int i=1; i<=n; i+=1) dq.push_back({a[i], i});
  28.     sort(all(dq), greater<pair<int,int>>());
  29.     set<int>se;
  30.     for(int i=1; i<=n; i+=1) se.insert(i);
  31.     for(int i=0; i<n; i+=1)
  32.     {
  33.         int need = dq[i].fi, loc = dq[i].se;
  34.         bool ok = 1;
  35.         if(clone.empty()) ok = 0;
  36.         else
  37.         {
  38.             int tmp = *clone.rbegin();
  39.             // if(loc == 4)
  40.             // {
  41.             //     for(auto j: clone) cout<<truoc[j]<<" "<<sau[j]<<'\n';
  42.             // }
  43.             if(max(truoc[tmp], sau[tmp]) == need) ok = 1;
  44.             else ok = 0;
  45.         }
  46.         if(!ok)
  47.         {
  48.             ans++;
  49.             auto tmp = se.upper_bound(loc);
  50.             if(tmp == se.end()) sau[ans] = 0;
  51.             else sau[ans] = a[*tmp];
  52.             tmp = se.lower_bound(loc);
  53.             if(tmp == se.begin()) truoc[ans] = 0;
  54.             else
  55.             {
  56.                 tmp--;
  57.                 truoc[ans] = a[*tmp];
  58.             }
  59.             clone.insert(ans);
  60.         }
  61.         else
  62.         {
  63.             int cur = *clone.rbegin();
  64.             // cout<<truoc[cur]<<" "<<sau[cur]<<'\n';
  65.             clone.erase(cur);
  66.             if(sau[cur] == need)
  67.             {
  68.                 auto tmp = se.upper_bound(loc);
  69.                 if(tmp == se.end()) sau[cur] = 0;
  70.                 else sau[cur] = a[*tmp];
  71.             }
  72.             else
  73.             {
  74.                 auto tmp = se.lower_bound(loc);
  75.                 if(tmp == se.begin()) truoc[cur] = 0;
  76.                 else
  77.                 {
  78.                     tmp--;
  79.                     truoc[cur] = a[*tmp];
  80.                 }
  81.             }
  82.             // cout<<truoc[cur]<<" "<<sau[cur]<<'\n';
  83.             clone.insert(cur);
  84.         }
  85.         se.erase(loc);
  86.     }
  87.     cout<<ans<<'\n';
  88. }
  89.  
  90. int32_t main()
  91. {
  92.     ios_base::sync_with_stdio(0); cin.tie(0);
  93.     int test=1;
  94.     cin>>test;
  95.     while(test--)
  96.     {
  97.         cin>>n;
  98.         for(int i=0; i<=n+1; i+=1) a[i] = 0;
  99.         for(int i=1; i<=n; i+=1) cin>>a[i];
  100.         solve();
  101.     }
  102. }
Success #stdin #stdout 0.01s 7696KB
comments (?)
stdin
copy 
4
5
4 3 2 1 5
3
1 1 1
6
7 8 1 5 9 2
10
1 7 9 7 1 10 2 10 10 7
stdout
copy 
2
1
2
4
https://ideone.com/7rnOoN
language:
C++14 (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!