結果
問題 | No.1188 レベルX門松列 |
ユーザー |
![]() |
提出日時 | 2020-08-22 14:53:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 3,345 bytes |
コンパイル時間 | 2,402 ms |
コンパイル使用メモリ | 197,240 KB |
最終ジャッジ日時 | 2025-01-13 08:59:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#if loc||local #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<(n);++i) using ll = int_fast64_t; using pll = pair<ll,ll>; constexpr ll INF = 1LL<<60; constexpr ll MOD = 1e9+7; template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;} template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;} #if loc||local template<class T>void dump(T&& t){cerr<<t<<endl;} template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);} #else void dump(){} template<class T,class... Ts> void dump(T&& h, Ts&&... t){} #endif template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;} template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;} template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;} template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;} template<class T>vector<T> vec(size_t a){return vector<T>(a);} template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));} ll LIS(const vector<ll>& v){ ll n=((ll)v.size()); constexpr ll INF = (1LL<<60); vector<ll> lis(n+1,INF); lis[0]=-INF; for(ll i=0;i<n;++i){ auto itr = lower_bound(lis.begin(),lis.end(),v[i]); *itr=min(*itr,v[i]); } ll len=0; for(ll i=1;i<=n;++i){ if(lis[i]!=INF)len=i; } return len; } signed main(){ ll n; cin>>n; vector<ll> a(n); cin>>a; vector<ll> lef_inc(n),rig_inc(n); vector<ll> lef_dec(n),rig_dec(n); { vector<ll> lis(n+1,INF); lis[0] = 0; ll len = 0; for(int i=0;i<n;++i){ auto itr = lower_bound(begin(lis),end(lis),a[i]); ll val = *itr; *itr = min<ll>(val,a[i]); if(lis[len+1]!=INF){ len++; } lef_inc[i] = len; } dump(lef_inc); } { vector<ll> lis(n+1,INF); lis[0] = 0; reverse(begin(a),end(a)); ll len = 0; for(int i=0;i<n;++i){ auto itr = lower_bound(begin(lis),end(lis),a[i]); ll val = *itr; *itr = min<ll>(val,a[i]); if(lis[len+1]!=INF){ len++; } rig_inc[i] = len; } reverse(begin(rig_inc),end(rig_inc)); reverse(begin(a),end(a)); dump(rig_inc); } { vector<ll> lis(n+1,-INF); lis[0] = INF; ll len = 0; for(int i=0;i<n;++i){ auto itr = lower_bound(begin(lis),end(lis),a[i],greater<>()); ll val = *itr; *itr = max<ll>(val,a[i]); if(lis[len+1]!=-INF)len++; lef_dec[i] = len; } dump(lef_dec); } { vector<ll> lis(n+1,-INF); lis[0] = INF; ll len = 0; reverse(begin(a),end(a)); for(int i=0;i<n;++i){ auto itr = lower_bound(begin(lis),end(lis),a[i],greater<>()); ll val = *itr; *itr = max<ll>(val,a[i]); if(lis[len+1]!=-INF)len++; rig_dec[i] = len; } reverse(begin(rig_dec),end(rig_dec)); reverse(begin(a),end(a)); dump(rig_dec); } ll ans = 0; for(int i=1;i+1<n;++i){ ll ushi = min(lef_inc[i]-1,rig_inc[i]-1); ll tapu = min(lef_dec[i]-1,rig_dec[i]-1); ll nichia = max(ushi,tapu); chmax(ans,nichia); } cout<<(ans)<<endl; }