結果
問題 | No.930 数列圧縮 |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#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); }