結果
問題 | No.1804 Intersection of LIS |
ユーザー |
![]() |
提出日時 | 2022-01-08 00:51:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 3,466 bytes |
コンパイル時間 | 1,247 ms |
コンパイル使用メモリ | 109,444 KB |
実行使用メモリ | 14,268 KB |
最終ジャッジ日時 | 2024-11-14 09:20:10 |
合計ジャッジ時間 | 5,676 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<queue> #include<deque> #include<iomanip> #include<tuple> #include<cassert> #include<set> #include<complex> #include<numeric> #include<functional> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long int LL; typedef pair<int,int> P; typedef pair<LL,LL> LP; const int INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(LL *array,int array_n,char middle=' '){ for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n')); } void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n')); } template<typename T> ostream& operator<<(ostream& os,const vector<T>& v1){ int n=v1.size(); for(int i=0;i<n;i++){ if(i)os<<" "; os<<v1[i]; } return os; } template<typename T1,typename T2> ostream& operator<<(ostream& os,const pair<T1,T2>& p){ os<<p.first<<" "<<p.second; return os; } template<typename T> istream& operator>>(istream& is,vector<T>& v1){ int n=v1.size(); for(int i=0;i<n;i++)is>>v1[i]; return is; } template<typename T1,typename T2> istream& operator>>(istream& is,pair<T1,T2>& p){ is>>p.first>>p.second; return is; } template<typename T> class bit{ private: vector<T> bit_vec; int bit_N=20; T bit_comp(T a,T b){ return max(a,b); } public: bit(int n){ for(bit_N=0;bit_N<30;bit_N++){ if(n<(1<<bit_N))break; } bit_vec.assign((1<<bit_N),0); } void set(int pos,T x){ bit_vec[pos]=bit_comp(bit_vec[pos],x); for(int i=0;i<bit_N;i++){ if(pos&(1<<i))continue; pos|=(1<<i); bit_vec[pos]=bit_comp(bit_vec[pos],x); } } T search(int pos){ T s=bit_vec[pos]; for(int i=0;pos>=(1<<i);i++){ if(pos&(1<<i))continue; pos-=(1<<i); s=bit_comp(s,bit_vec[pos]); } return s; } }; namespace sol{ void solve(){ int n,m; int i,j,k; int a,b,c; cin>>n; vector<int> v1(n); vector<int> va(n+1),vb(n+1); cin>>v1; for(i=0;i<n;i++)v1[i]--; bit<int> bt(n); for(i=0;i<n;i++){ a=bt.search(v1[i]); bt.set(v1[i],a+1); va[i]=a; } c=bt.search(n-1); bit<int> bt2(n); for(i=n-1;i>=0;i--){ b=n-1-v1[i]; a=bt2.search(b); bt2.set(b,a+1); vb[i]=a; } vector<int> cnt(n); for(i=0;i<n;i++){ if(va[i]+vb[i]!=c-1)continue; cnt[va[i]]++; } vector<int> vs; for(i=0;i<n;i++){ if(va[i]+vb[i]!=c-1)continue; if(cnt[va[i]]==1)vs.push_back(v1[i]+1); } cout<<vs.size()<<endl; cout<<vs<<endl; } } int main(){ cin.tie(0); ios::sync_with_stdio(false); sol::solve(); }