結果
問題 | No.930 数列圧縮 |
ユーザー | IKyopro |
提出日時 | 2019-11-22 23:11:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 2,101 bytes |
コンパイル時間 | 1,307 ms |
コンパイル使用メモリ | 89,904 KB |
最終ジャッジ日時 | 2025-01-08 05:22:24 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <iostream>#include <vector>#include <functional>#include <cassert>using namespace std;using ll = long long;template<class T> using vec = vector<T>;template<class T> using vvec = vector<vec<T>>;template<typename Monoid>class SegmentTree{private:using F = function<Monoid(Monoid,Monoid)>;int sz;vector<Monoid> seg;const F op;//演算const Monoid e;//単位元public:SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){sz = 1;while(sz<n) sz <<= 1;seg.assign(2*sz,e);}//代入void set(int k, const Monoid &x){seg[k+sz] = x;}//前計算(?)void build(){for(int i=sz-1;i>0;i--){seg[i] = op(seg[2*i],seg[2*i+1]);}}void update(int k,const Monoid &x){k += sz;seg[k] += x;while(k>>=1){seg[k] = op(seg[2*k],seg[2*k+1]);}}Monoid query(int l,int r){Monoid L = e,R = e;for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){if(l&1) L = op(L,seg[l++]);if(r&1) R = op(seg[--r],R);}return op(L,R);}Monoid operator[](const int &k)const{return seg[k+sz];}};int main(){int N;cin >> N;vec<int> P(N),Q(N);for(int i=0;i<N;i++){cin >> P[i];P[i]--;Q[P[i]] = i;}SegmentTree<int> seg(N+1,[](int a,int b){return max(a,b);},-1);int l = 0;for(int i=0;i<N;i++) seg.set(i,P[i]);seg.build();vector<int> ans;for(int i=N-1;i>=0;i--){int ma = seg.query(Q[i]+1,N);if(ma==-1){for(int j=Q[i]-1;j>=0;j--) if(P[j]!=-1) ans.push_back(P[j]);break;}else{if(Q[i]==l){cout << "No" << endl;return 0;}ans.push_back(i);seg.update(Q[i],-1);P[Q[i]] = -1;while(Q[l]==-1) l++;}}cout << "Yes" << endl;for(int i=0;i<N-1;i++) cout << ans[i]+1 << (i!=N-2? " ":"\n");assert(ans.size()==N-1);}