結果

問題 No.930 数列圧縮
ユーザー IKyopro
提出日時 2019-11-22 22:36:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,289 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 100,184 KB
最終ジャッジ日時 2025-01-08 05:17:05
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 12 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <functional>
#include <stack>
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);
    for(int i=0;i<N;i++){
        cin >> P[i];
        P[i]--;
    }
    SegmentTree<int> seg(N,[](int a,int b){return a+b;},0);
    SegmentTree<int> seg2(N,[](int a,int b){return a+b;},0);
    vec<int> op(N,0);
    int sum = 0;
    for(int i=0;i<N;i++){
        seg.update(P[i],1);
        op[i] = seg.query(0,P[i])-seg2.query(0,P[i]);
        seg2.update(P[i],op[i]);
        sum += op[i];
//        cerr << op[i] << endl;
    }
    if(sum<N-1){
        cout << "No" << endl;
        return 0;
    }
    vector<int> ans;
    stack<int> st;
    for(int i=0;i<N;i++){
        if(op[i]==0) st.push(P[i]);
        else{
            if(op[i]==1) ans.push_back(P[i]);
            else{
                while(op[i]!=1 && !st.empty()){
                    ans.push_back(st.top()); st.pop();
                    op[i]--;
                }
                if(op[i]==1) ans.push_back(P[i]);
            }
        }
    }
    cout << "Yes" << endl;
    for(int i=0;i<N-1;i++) cout << ans[i]+1 << (i!=N-2? " ":"\n");
}
0