結果
問題 | No.1804 Intersection of LIS |
ユーザー |
![]() |
提出日時 | 2022-01-07 22:58:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 2,164 bytes |
コンパイル時間 | 861 ms |
コンパイル使用メモリ | 79,472 KB |
最終ジャッジ日時 | 2025-01-27 09:44:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream>#include <vector>using namespace std;typedef long long ll;ll INF = 1000000000000000;struct segment_tree{int n; vector<ll> seg;segment_tree(){}segment_tree(int sz){n = sz; seg.resize(2*n);}segment_tree(vector<ll> v){n = v.size(); seg.resize(2*n);for(int i=0;i<n;i++) seg[i + n] = v[i];for(int i=n - 1;i>0;i--) seg[i] = max(seg[i<<1],seg[i<<1|1]);}void init(int sz){n = sz; seg.resize(2*n);}void update(int p,ll val){for(seg[p += n] = val;p>1;p>>=1) seg[p>>1] = max(seg[p],seg[p^1]);}ll query(int l,int r){ll res = -INF;for(l += n,r += n; l<r;l>>=1,r>>=1){if(l&1) res = max(res,seg[l++]);if(r&1) res = max(res,seg[--r]);}return res;}int bin(int l,ll x){//seg.query(l,r - 1)<x,seg,qeury(l,r)>=x, return r;int le = l,ri = n;while(ri - le>1){int mid = (le + ri)/2;if(query(l,mid)>=x) ri = mid;else le = mid;}return ri;}void clear(){for(int i=0;i<2*n;i++) seg[i] = 0;}};int a[300010];int main(){int i,n; cin >> n;for(i=0;i<n;i++) cin >> a[i];segment_tree seg(n + 1);vector<int> l(n),r(n);for(i=0;i<n;i++){l[i] = seg.query(0,a[i]) + 1;seg.update(a[i],l[i]);}seg.clear();for(i=n - 1;i>=0;i--){r[i] = seg.query(a[i],n + 1) + 1;seg.update(a[i] - 1,r[i]);}int len = seg.query(0,n + 1);vector<int> used;for(i=0;i<n;i++){if(l[i] + r[i]==len + 1) used.push_back(a[i]);}int k = used.size();vector<bool> le(k),ri(k);int mx = -1;for(i=0;i<k;i++){if(mx<used[i]) le[i] = true;else le[i] = false;mx = max(mx,used[i]);}int mn = n + 1;for(i=k - 1;i>=0;i--){if(used[i]<mn) ri[i] = true;else ri[i] = false;mn = min(mn,used[i]);}vector<int> ans;for(i=0;i<k;i++){if(le[i] && ri[i]) ans.push_back(used[i]);}cout << ans.size() << endl;for(int x:ans) cout << x << " ";cout << endl;}