fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define file "o"
  8. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  9. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  10. #define nl "\n"
  11. #define ss " "
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=998244353;
  49. const int maxn=3e5+15;
  50. const ll inf=1e18;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. int n, a[maxn], pmin[maxn], pmax[maxn], smin[maxn], smax[maxn];
  72. bool nxt[maxn];
  73.  
  74. void solve()
  75. {
  76.     cin>>n;
  77.     ff(i, 1, n) cin>>a[i];
  78.     pmin[0]=mod; pmax[0]=-mod; smin[0]=mod; smax[0]=-mod;
  79.     pmin[n+1]=mod; pmax[n+1]=-mod; smin[n+1]=mod; smax[n+1]=-mod;
  80.     ff(i, 1, n) pmin[i]=min(pmin[i-1], a[i]), pmax[i]=max(pmax[i-1], a[i]);
  81.     ffr(i, n, 1) smin[i]=min(smin[i+1], a[i]), smax[i]=max(smax[i+1], a[i]);
  82.  
  83.     vi q; q.pb(1);
  84.     int ans=0;
  85.  
  86.     ff(k, 1, n)
  87.     {
  88.         vi nq;
  89.         for(int l : q)
  90.         {
  91.             int r=n-k+l-1, low=mod, high=-mod;
  92.             if(l>1) low=pmin[l-1], high=pmax[l-1];
  93.             if(r<n) mini(low, smin[r+1]), maxi(high, smax[r+1]);
  94.  
  95.             if(a[l]<low || a[l]>high)
  96.             {
  97.                 if(!nxt[l+1]) { nxt[l+1]=1; nq.pb(l+1); }
  98.             }
  99.             if(l<r && (a[r]<low || a[r]>high))
  100.             {
  101.                 if(!nxt[l]) { nxt[l]=1; nq.pb(l); }
  102.             }
  103.         }
  104.         if(nq.empty()) break;
  105.         ans=k;
  106.         q = move(nq);
  107.         for(int l : q) nxt[l]=0; 
  108.     }
  109.     cout<<ans<<nl;
  110. }
  111.  
  112. signed main()
  113. {
  114.     rf();
  115.     int tt; cin>>tt;
  116.     while(tt--) solve();
  117.     re;
  118. }
Success #stdin #stdout 0.01s 7700KB
comments (?)
stdin
copy 
3
5
3 1 4 1 5
3
2 2 1
16
3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2
stdout
copy 
2
1
10
https://ideone.com/MXWmmb
language:
C++14 (gcc 8.3)
created:
6 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!