fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i,a,b) for (int i=(a); i<=(b); ++i)
  8. #define nl "\n"
  9. #define pb emplace_back
  10. using pii = pair<int,int>;
  11.  
  12. inline void rf() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.     if (fopen(file".inp","r")) {
  16.         freopen(file".inp","r",stdin);
  17.         freopen(file".out","w",stdout);
  18.     }
  19. }
  20.  
  21. int main() {
  22.     rf();
  23.     int n; 
  24.     if(!(cin>>n)) return 0;
  25.     vector<pii> v; v.reserve(n);
  26.     ff(i,1,n){ int x; cin>>x; v.pb(x,i); }
  27.     sort(v.begin(), v.end()); // tăng dần theo giá trị
  28.  
  29.     // danh sách liên kết các chỉ số còn sống: 1..n
  30.     vector<int> L(n+2), R(n+2);
  31.     L[0]=0; R[0]=1;
  32.     ff(i,1,n){ L[i]=i-1; R[i]=i+1; }
  33.     R[n]=n+1; L[n+1]=n;
  34.  
  35.     // đếm khoảng cách giữa hai chỉ số còn sống kề nhau
  36.     vector<int> cnt(n+2,0);
  37.     if(n>=2) cnt[1]=n-1;
  38.     int mx = (n>=2?1:0);
  39.  
  40.     auto add_cnt = [&](int d, int delta){
  41.         if (d<=0 || d>n) return;
  42.         cnt[d] += delta;
  43.         if (delta>0 && d>mx) mx=d;
  44.     };
  45.     auto shrink_mx = [&](){
  46.         while (mx>0 && cnt[mx]==0) --mx;
  47.     };
  48.  
  49.     auto del = [&](int i){
  50.         int l=L[i], r=R[i];
  51.         if (l>=1) add_cnt(i-l, -1);
  52.         if (r<=n) add_cnt(r-i, -1);
  53.         if (l>=1 && r<=n) add_cnt(r-l, +1);
  54.         // unlink i
  55.         R[l]=r; L[r]=l;
  56.     };
  57.  
  58.     int j=0;
  59.     ff(i,1,n){
  60.         while (j<n && v[j].first < i) { 
  61.             del(v[j].second); 
  62.             ++j;
  63.         }
  64.         shrink_mx();                // đảm bảo mx là khoảng cách lớn nhất hiện tại
  65.         if (mx <= i) {              // điều kiện tương đương với *s.rbegin() <= i trước đây
  66.             cout << i;
  67.             return 0;
  68.         }
  69.     }
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
10
10 1 2 0 3 4 5 0 2 10
stdout
copy 
2
https://ideone.com/JcsWtJ
language:
C++14 (gcc 8.3)
created:
9 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!