fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1LL << (n))
  6. #define TASK ""
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8. #define lc(n) (n << 1)
  9. #define rc(n) ((n << 1) | 1)
  10.  
  11. #define fi first
  12. #define se second
  13. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  14. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  15.  
  16. #define mii map<int,int>
  17. #define umi unordered_map<int, int>
  18. #define pii pair<int,int>
  19. #define vi vector<int>
  20.  
  21. using namespace std;
  22.  
  23. const int oo = 1e9 + 1;
  24. const int mod = 20262026;
  25. const int nmax = 1e6 + 8;
  26. const int base = 311;
  27.  
  28. int n, a[nmax], r[nmax];
  29.  
  30. stack<int> s, is;
  31.  
  32. int calc(int l, int r){
  33.     return r - l + 1;
  34. }
  35.  
  36. main(){
  37.     fast;
  38.     openfile();
  39.     cin >> n;
  40.     s.push(0);
  41.     a[0] = -oo;
  42.     is.push(n + 1);
  43.     a[n + 1] = -oo;
  44.     for(int i = 1;i <= n; ++i) cin >> a[i];
  45.     for(int i = n; i >= 1; --i){
  46.         while(a[i] <= a[is.top()]){
  47.             is.pop();
  48.         }
  49.         r[i] = is.top();
  50.         is.push(i);
  51. //        cout << r[]
  52.     }
  53.     int ans = 0;
  54.     for(int i = 1; i <= n; ++i){
  55.         while(a[i] <= a[s.top()]){
  56.             s.pop();
  57.         }
  58.         if(calc(s.top() + 1, r[i] - 1) >= a[i]) ans = max(ans, a[i]);
  59.         s.push(i);
  60.     }
  61.     cout << ans;
  62. }
  63.  
Success #stdin #stdout 0.01s 5664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R9yKPu
language:
C++14 (gcc 8.3)
created:
12 hours 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!