結果

問題 No.318 学学学学学
ユーザー rapurasu
提出日時 2019-02-19 03:00:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 4,291 bytes
コンパイル時間 2,244 ms
コンパイル使用メモリ 182,928 KB
実行使用メモリ 22,032 KB
最終ジャッジ日時 2024-06-22 18:48:50
合計ジャッジ時間 6,836 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
//根ノードを1としているので，
//左の子:k*2
//右の子:k*2+1
//親:floor(k/2)
//となる．
//根ノードを1とすると非再帰が書きやすい(二進数的性質が優れているため)のだが，
//再帰的に書くのであればどちらでも問題ない．
//int maxi[N*2];
//int lazy[N*2];
namespace LST_{
    using RET = LL;//葉の個数
    constexpr int BUF =1048576+20;
    RET t[BUF];
    int ptr=0;
    inline RET* get(const int size){
        ptr+=size;
        return t+ptr-size;
    }
    
}
struct LazySegTree{
    using T=LST_::RET;
    T* maxi;//ノードkに対応する区間の最大値
    T* lazy;//lazy[k]はノードkの配下全体をlazy[k]で塗りつぶすという命令を表す．lazy[k]=NILのときは何もしないと約束する.
    static const T NIL = 1e9+8;//lazyがこの値の時は更新しない
    //2^20=1048576, 2^19= 524288
    //2^18=262144,  2^17= 131072(2のべきでないといけない)
    static const int N = 262144;
    LazySegTree(){
        maxi=LST_::get(2*N);//最大値の配列の確保
        lazy=LST_::get(2*N);//遅延の確保
        //更新用
        REP(i,N+10){
            lazy[i]=NIL;
            maxi[i]=0;
        }
        //加算用
        //REP(i,2*N){
        //  lazy[i]=0;
        //  maxi[i]=0;
        //}
    }
    
    //kをvで塗りつぶす
    void setLazy(int k,T v){
        //更新用
        lazy[k]=v;
        maxi[k]=v;
        //加算用
        //lazy[k]+=v;
        //maxi[k]+=v;
    }
    void push(int k){
        //遅延命令がなにもなければ何もしない
        //更新用
        if(lazy[k]==NIL){
            return;
        }
        //加算用
        //if(lazy[k]==0){
        //  return;
        //}
        setLazy(k*2+0,lazy[k]);
        setLazy(k*2+1,lazy[k]);
        //子に命令を伝搬させたので，命令を空にする
        lazy[k] =NIL;
        //lazy[k]=0;//加算用
    }
    //最大値を求める
    T compar(T a, T b){
        return max(a,b);
        //return min(a,b);最小値を求める場合はこっちを使う
    }
    
    void fix(int k){
        //ノードkに対応する区間の最大値は，「左の子の最大値」と「右の子の最大値」の最大値
        maxi[k]=compar(maxi[k*2],maxi[k*2+1]);
    }
    //区間[queryL,queryR)をvalで塗りつぶす
    void fill(int queryL, int queryR, T val, int k=1,int nodeL =0,int nodeR=N){
         //クエリ区間とノード区間が交差していないのなら，これ以上，処理する必要はない
        if(nodeR <= queryL || queryR<=nodeL){
            return;
        }
        //ノード区間がクエリ区間に完全に覆われたら，遅延命令をセットして，さっさと帰る
        if(queryL <= nodeL && nodeR<=queryR){
            setLazy(k,val);
            return;
        }
        //ノードが下がる時には命令をpushする
        push(k);
        int nodeM =(nodeL + nodeR) /2;
        fill(queryL,queryR, val, k*2+0,nodeL, nodeM);
        fill(queryL,queryR, val ,k*2+1,nodeM, nodeR);
        //ノードが上がる時には情報をfixする
        fix(k);
    }
    //区間[queryL,queryR)の最大値を求める
    T maximum(int queryL, int queryR, int k=1,int nodeL=0,int nodeR =N){
        //クエリ区間とノード区間が交差していない
        if(nodeR<=queryL||queryR<=nodeL){
            return -(1e15);
        }
        //ノード区間がクエリ区間に完全に覆われた
        if(queryL <= nodeL && nodeR <=queryR){
            return maxi[k];
        }
        //ノードが下がるときは命令をpushする
        push(k);
        int nodeM =(nodeL+nodeR)/2;
        T vl =maximum(queryL,queryR, k*2+0,nodeL,nodeM);
        T vr =maximum(queryL,queryR, k*2+1,nodeM,nodeR);
        return compar(vl,vr);
    }
};
void show(int N,LazySegTree seg){
    REP(i,N){
        int a=seg.maximum(i,i+1);
        /*if(a%2==0){
            cout<<0;
        }else{
            cout<<1;
        }*/
        cout<<a;
        if(i!=N-1)cout<<" ";
    }
    cout<<endl;
}
vector<LL>v[100011];
map<int,int>m;
int a[100001];
int main(){
    int N;
    cin>>N;
    vector<int>w;
    REP(i,N){
        cin>>a[i];
        w.push_back(a[i]);
    }
    sort(w.begin(),w.end());
    w.erase(unique(w.begin(),w.end()),w.end());
    REP(i,w.size()){
        m[w[i]]=i+1;
    }
    LazySegTree seg;
    REP(i,N){
        seg.fill(i,i+1,a[i]);
        v[m[a[i]]].push_back(i);
    }
    REP(i,100011){
        REP(j,v[i].size()){
            if(j!=v[i].size()-1){
                seg.fill(v[i][j],v[i][j+1],w[i-1]);
            }
            seg.fill(v[i][j],v[i][j]+1,w[i-1]);
        }
    }
    show(N,seg);
    return(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0