fork download 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define f first
  4. #define sc second
  5. using namespace std;
  6. typedef long long int ll;
  7. typedef string str;
  8. struct segtree{
  9.     const ll inf = 1e18;
  10.     int k;
  11.     vector<ll> mx;
  12.     segtree(int n){
  13.         k = 1;
  14.         while(k <= n) k*=2; k*=2;
  15.         mx.assign(k, -inf);
  16.     }
  17.     void upd(int in, ll x){
  18.         in+=k/2;
  19.         mx[in] = x, in/=2;
  20.         while(in > 0){
  21.             mx[in] = max(mx[2*in], mx[2*in+1]);
  22.             in/=2;
  23.         }
  24.     }
  25.     ll smx(int l, int r, int nd, int a, int b){
  26.         if(b < l || a > r) return -inf;
  27.         if(a >= l && b <= r) return mx[nd];
  28.         int c = (a+b)/2;
  29.         return max(smx(l, r, 2*nd, a, c), smx(l, r, 2*nd+1, c+1, b));
  30.     }
  31.     ll smx(int l, int r){
  32.         return smx(l, r, 1, 0, k/2-1);
  33.     }
  34. };
  35. int main(){
  36.     ios_base::sync_with_stdio(0);
  37.     cin.tie(0);
  38.     int n; cin >> n;
  39.     vector<int> v(n);
  40.     for(int &x: v) cin >> x;
  41.     vector<int> pref(n, 0), suff(n, 0);
  42.     for(int i = 0; i < n; i++){
  43.         if(i != 0 && v[i] > v[i-1]){
  44.             pref[i] = pref[i-1]+1;
  45.         }
  46.         else pref[i] = 1;
  47.     }
  48.     for(int i = n-1; i >= 0; i--){
  49.         if(i != n-1 && v[i] > v[i+1]){
  50.             suff[i] = suff[i+1]+1;
  51.         }
  52.         else suff[i] = 1;
  53.     }
  54.     vector<int> pref1(n, 0), suff1(n, 0); 
  55.     for(int i = 0; i < n; i++){
  56.         if(i != 0 && v[i] < v[i-1]) pref1[i] = pref1[i-1]+1;
  57.         else pref1[i] = 1;
  58.     }
  59.     for(int i = n-1; i >= 0; i--){
  60.         if(i != n-1 && v[i] < v[i+1]) suff1[i] = suff1[i+1]+1;
  61.         else suff1[i] = 1;
  62.     }
  63.     segtree seg(n);
  64.     for(int i = 0; i < n; i++){
  65.         seg.upd(i, max(suff1[i], pref1[i]));
  66.     }
  67.     int ans = 0;
  68.     for(int i = 1; i < n-1; i++){
  69.         if(v[i] < v[i+1] || v[i] < v[i-1]) continue;
  70.         int a = i-pref[i], b = i+suff[i];
  71.         int mx = max(pref[i], suff[i]);
  72.         if(a >= 0 && seg.smx(0, a) >= mx || suff1[a] >= mx){
  73.             continue;
  74.         }
  75.         if(b < n && seg.smx(b, n-1) >= mx || pref1[b] >= mx){
  76.             continue;
  77.         }
  78.         a = pref[i], b = suff[i];
  79.         if(a < b) swap(a, b);
  80.         if(a == b && a%2 == 1){
  81.             ans++;
  82.             continue;
  83.         }
  84.     }
  85.     /*
  86.     a
  87.     */
  88.     cout << ans << "\n";
  89. }
Success #stdin #stdout 0s 4916KB
comments (?)
stdin 
5
1 2 5 4 3
stdout 
1
https://ideone.com/YGCPxT
language:
C++14 (gcc 8.3)
created:
3 years 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!