結果
問題 |
No.1188 レベルX門松列
|
ユーザー |
![]() |
提出日時 | 2020-08-22 13:48:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 3,415 bytes |
コンパイル時間 | 1,441 ms |
コンパイル使用メモリ | 120,356 KB |
実行使用メモリ | 10,500 KB |
最終ジャッジ日時 | 2024-10-15 08:02:57 |
合計ジャッジ時間 | 3,961 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} #include <functional> #include <climits> //SegmentTree<int> seg(N,[](int a,int b){return min(a,b);},INT_MAX); template< typename T> class SegmentTree{ public: using F = function<T(T,T)>; int n; vector<T> tree; F operation; T def; SegmentTree(int size,F _operation,T _def):operation(_operation),def(_def){ n=1; while(n<size) n*=2; tree.resize(2*n-1,def); } SegmentTree(){} void embody(int size,F _operation,T _def){ operation=_operation; def=_def; n=1; while(n<size) n*=2; tree.resize(2*n-1,def); } void initialize(vector<T> v){ int vSize=v.size(); n=1; while(n<vSize) n*=2; tree.resize(2*n-1,def); for(int i=0;i<vSize;i++) tree[i+n-1]=v[i]; for(int i=n-2;i>=0;i--) tree[i]=operation(tree[2*i+1],tree[2*i+2]); } void update(int index,T value){ index+=n-1; tree[index]=value; while(index>0){ index=(index-1)/2; tree[index]=operation(tree[2*index+1],tree[2*index+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1){//[a,b),getMin(a,b,0,0,-1) if(r<0) r=n; if(r<=a||b<=l) return def; else if(a<=l&&r<=b) return tree[k]; else{ T lval=query(a,b,2*k+1,l,(l+r)/2); T rval=query(a,b,2*k+2,(l+r)/2,r); return operation(lval,rval); } } int find(int x,int k=0,int l=0,int r=-1){// a[0]+...+a[i]>=x (i:minimal) if(r<0) r=n; if(r-l==1) return k-(n-1); if(tree[2*k+1]>=x) return find(x,2*k+1,l,(l+r)/2); else return find(x-tree[2*k+1],2*k+2,(l+r)/2,r); } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin>>N; vector<int> A(N); rep(i,N) cin>>A[i]; vector<int> B=A; sort(all(B)); B.erase(unique(all(B)),B.end()); int V=B.size(); map<int,int> mp; rep(i,V) mp[B[i]]=i; rep(i,N) A[i]=mp[A[i]]; int ans=0; { vector<int> lef(N,N); { SegmentTree<int> seg(V+1,[](int a,int b){return max(a,b);},0); rep(i,N){ int val=seg.query(A[i]+1,V); lef[i]=val; seg.update(A[i],val+1); } } vector<int> rig(N,N); { SegmentTree<int> seg(V+1,[](int a,int b){return max(a,b);},0); for(int i=N-1;i>=0;i--){ int val=seg.query(A[i]+1,V); rig[i]=val; seg.update(A[i],val+1); } } for(int i=0;i<N;i++){ chmax(ans,min(lef[i],rig[i])); } } { vector<int> lef(N,N); { SegmentTree<int> seg(V+1,[](int a,int b){return max(a,b);},0); rep(i,N){ int val=seg.query(0,A[i]); lef[i]=val; seg.update(A[i],val+1); } } vector<int> rig(N,N); { SegmentTree<int> seg(V+1,[](int a,int b){return max(a,b);},0); for(int i=N-1;i>=0;i--){ int val=seg.query(0,A[i]); rig[i]=val; seg.update(A[i],val+1); } } for(int i=0;i<N;i++){ chmax(ans,min(lef[i],rig[i])); } } cout<<ans<<endl; return 0; }