fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace{
  6.     // Types
  7.     #define ll long long
  8.     #define ull unsigned long long
  9.  
  10.     // Shortcuts
  11.     #define sp " "
  12.     #define endl "\n"
  13.     #define ft first
  14.     #define se second
  15.     #define pb push_back
  16.     #define pob pop_back
  17.     #define __Orion__ signed main()
  18.     #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  19.     #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  20.  
  21.     // Functions
  22.     #define sz(s) (s).size()
  23.     #define all(s) (s).begin(), (s).end()
  24.     #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  25.     #define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  26.     #define file(a) freopen(a".INP", "r", stdin); freopen(a".OUT", "w", stdout)
  27.  
  28.     // Const
  29.     const ll inf = 1e18;
  30.     const ll mod = 1e9 + 7;
  31.     const double pi = 3.1415926535897932384626433832795;
  32. }
  33. const int mx = 2e6 + 5;
  34. int n, ans, maxx, t, s[mx], ma[mx], pos[mx];
  35. stack<int> st;
  36.  
  37. __Orion__{
  38.     fast;
  39.     //file("test1");
  40.  
  41.     cin >> n;
  42.     FOR(i, 1, n) cin >> s[i];
  43.     FOR(i, 1, n){
  44.         if(s[i] > ma[i - 1]) t++;
  45.         ma[i] = max(ma[i - 1], s[i]);
  46.         pos[i] = t;
  47.     }
  48.  
  49.     FORD(i, n, 1){
  50.         while(!st.empty() && st.top() <= s[i]) st.pop();
  51.         st.push(s[i]);
  52.         if(sz(st) == 1) maxx = st.top();
  53.  
  54.         auto it = upper_bound(ma + 1, ma + n + 1, maxx);
  55.         int p = it - ma, k = sz(st);
  56.         if(p < i) k+=pos[i - 1] - pos[p] + 1;
  57.         ans = max(ans, k);
  58.     }
  59.     cout << ans;
  60.     cerr << "Time elapsed: " << TIME  << sp << "s." << endl;
  61.  
  62.     return (0 ^ 0);
  63. }
  64.  
Success #stdin #stdout #stderr 0.01s 5840KB
comments (?)
stdin
copy 
5
1 4 3 2 1
stdout
copy 
2
stderr
copy 
Time elapsed: 0.005745 s.
https://ideone.com/AzJB0g
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!