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];
  13.  
  14. struct custom_set
  15. {
  16.     bool operator()(int a1, int a2) const
  17.     {
  18.         auto k1 = max(a[truoc[a1]], a[sau[a1]]);
  19.         auto k2 = max(a[truoc[a2]], a[sau[a2]]);
  20.         if (k1 != k2) return k1 > k2;
  21.         return a1 < a2;
  22.     }
  23. };
  24.  
  25. void solve()
  26. {
  27.     int ans = 0;
  28.     set<int, custom_set>clone;
  29.     deque<pair<int,int>>dq;
  30.     for(int i=1; i<=n; i+=1) dq.push_back({a[i], i});
  31.     sort(all(dq), greater<pair<int,int>>());
  32.     set<int>se;
  33.     for(int i=1; i<=n; i+=1) se.insert(i);
  34.     for(int i=0; i<n; i+=1)
  35.     {
  36.         int need = dq[i].fi, loc = dq[i].se;
  37.         // cout<<need<<'\n';
  38.         // for(auto j: clone)
  39.         // {
  40.         //     cout<<a[truoc[j]]<<" "<<a[sau[j]]<<'\n';
  41.         // }
  42.         // cout<<"_______________\n"<<'\n';
  43.         for(auto j: clone)
  44.         {
  45.             if(max(a[truoc[j]], a[sau[j]]) > need) clone.erase(j);
  46.             else break;
  47.         }
  48.         bool ok = 1;
  49.         if(clone.empty()) ok = 0;
  50.         else
  51.         {
  52.             int tmp = *clone.begin();
  53.             if(max(a[truoc[tmp]], a[sau[tmp]]) == need) ok = 1;
  54.             else ok = 0;
  55.         }
  56.         if(!ok)
  57.         {
  58.             ans++;
  59.             auto tmp = se.upper_bound(loc);
  60.             if(tmp == se.end()) sau[ans] = n+1;
  61.             else sau[ans] = *tmp;
  62.             tmp = se.lower_bound(loc);
  63.             if(tmp == se.begin()) truoc[ans] = 0;
  64.             else
  65.             {
  66.                 tmp--;
  67.                 truoc[ans] = *tmp;
  68.             }
  69.             clone.insert(ans);
  70.         }
  71.         else
  72.         {
  73.             int cur = *clone.begin();
  74.             clone.erase(cur);
  75.             // cout<<truoc[cur]<<" "<<sau[cur]<<'\n';
  76.             if(a[sau[cur]] >= a[truoc[cur]])
  77.             {
  78.                 loc = sau[cur];
  79.                 auto tmp = se.upper_bound(loc);
  80.                 if(tmp == se.end()) sau[cur] = n+1;
  81.                 else sau[cur] = *tmp;
  82.             }
  83.             else
  84.             {
  85.                 loc = truoc[cur];
  86.                 auto tmp = se.lower_bound(loc);
  87.                 if(tmp == se.begin()) truoc[cur] = 0;
  88.                 else
  89.                 {
  90.                     tmp--;
  91.                     truoc[cur] = *tmp;
  92.                 }
  93.             }
  94.             // cout<<truoc[cur]<<" "<<sau[cur]<<'\n';
  95.             clone.insert(cur);
  96.         }
  97.         // cout<<ok<<'\n';
  98.         se.erase(loc);
  99.     }
  100.     cout<<ans<<'\n';
  101. }
  102.  
  103. int32_t main()
  104. {
  105.     ios_base::sync_with_stdio(0); cin.tie(0);
  106.     int test=1;
  107.     cin>>test;
  108.     while(test--)
  109.     {
  110.         cin>>n;
  111.         for(int i=0; i<=n+1; i+=1) a[i] = 0, truoc[i] = sau[i] = 0;
  112.         for(int i=1; i<=n; i+=1) cin>>a[i];
  113.         solve();
  114.     }
  115. }
Success #stdin #stdout 0.01s 7604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VW4yid
language:
C++14 (gcc 8.3)
created:
6 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!