結果

問題 No.318 学学学学学
コンテスト
ユーザー ensembleaverage
提出日時 2024-04-02 00:12:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 222 ms / 2,000 ms
コード長 4,964 bytes
コンパイル時間 3,699 ms
コンパイル使用メモリ 260,184 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2024-09-30 22:56:05
合計ジャッジ時間 7,193 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

/*
#include "boost/multiprecision/cpp_int.hpp"
namespace mp = boost::multiprecision;
using i128=mp::cpp_int;
*/

using namespace std;
typedef long long ll;
typedef int64_t i64;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define drep(i,a,n) for(int i=a;i>n;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define iINF 1000000007
#define lINF 10000000000007
#define llINF 4000000000000000007
#define all(x) x.begin(),x.end()
#define so(x) sort(all(x))
#define re(x) reverse(all(x))
const double PI = acos(-1);

//遅延セグ木
template<typename S,S op(S l,S r),S e(),typename F,S mapping(F f,S prev),F composition(F f,F g),F id()>
struct lazysegment{
    vector<S> tree;
    vector<F> func;
    int x=2;
    lazysegment(vector<S> &data){ //nは数列の数 dataは数列の値(n個)
        int n=data.size();
        while(x<2*n) x*=2;
        tree.assign(x-1,e()); //(0~x-2)
        func.assign(x-1,id());
        int y=x/2;
        rep(i,y-1,x-1){
            if(i-y+1>=n) continue;
            tree[i]=data[i-y+1];
        }
        drep(i,y-2,-1){
            tree[i]=op(tree[2*i+1],tree[2*i+2]);
        }
    }
    
    lazysegment(int n){
        while(x<2*n) x*=2;
        tree.assign(x-1,e()); //(0~x-2)
        func.assign(x-1,id());
    }
    
    void update(int a,int b,int k,int l,int r,F f,F g){ //最初の入力はquery(a,b,0,0,x/2,やりたい処理,id())
        //[a,b)の取り出したい値を返す [l,r)は探索しているところ kはtreeのindex
        if(r<=a||b<=l){
            func[k]=composition(g,func[k]);
            tree[k]=mapping(func[k],tree[k]);
            if(k<x/2-1){
                func[2*k+1]=composition(func[k],func[2*k+1]);
                func[2*k+2]=composition(func[k],func[2*k+2]);
            }
            func[k]=id();
            return;
        }//[l,r)が[a,b)に含まれていない
        if(a<=l&&r<=b){
            func[k]=composition(composition(f,g),func[k]);
            tree[k]=mapping(func[k],tree[k]);
            if(k<x/2-1){
                func[2*k+1]=composition(func[k],func[2*k+1]);
                func[2*k+2]=composition(func[k],func[2*k+2]);
            }
            func[k]=id();
            return;
        }//[l,r)が[a,b)に内包されている
        func[k]=composition(g,func[k]);
        update(a,b,2*k+1,l,(r+l)/2,f,func[k]);
        update(a,b,2*k+2,(r+l)/2,r,f,func[k]);
        tree[k]=op(tree[2*k+1],tree[2*k+2]);
        func[k]=id();
        return;
    }
    
    S qu(int a,int b,int k,int l,int r,F f){ //入力はquery(a,b,0,0,x/2,id())
        //[a,b)の取り出したい値を返す [l,r)は探索しているところ kはtreeのindex
        if(r<=a||b<=l){
            func[k]=composition(f,func[k]);
            tree[k]=mapping(func[k],tree[k]);
            if(k<x/2-1){
                func[2*k+1]=composition(func[k],func[2*k+1]);
                func[2*k+2]=composition(func[k],func[2*k+2]);
            }
            func[k]=id();
            return e();
        }//[l,r)が[a,b)に含まれていない
        if(a<=l&&r<=b){
            func[k]=composition(f,func[k]);
            tree[k]=mapping(func[k],tree[k]);
            if(k<x/2-1){
                func[2*k+1]=composition(func[k],func[2*k+1]);
                func[2*k+2]=composition(func[k],func[2*k+2]);
            }
            func[k]=id();
            return tree[k];
        }//[l,r)が[a,b)に内包されている
        func[k]=composition(f,func[k]);
        S ans=op(qu(a,b,2*k+1,l,(r+l)/2,func[k]),qu(a,b,2*k+2,(r+l)/2,r,func[k]));
        tree[k]=op(tree[2*k+1],tree[2*k+2]);
        func[k]=id();
        return ans;
    }
};

//遅延セグ木
struct S{
    int x;
};

S op(S l,S r){
    //S×S→Sの写像
    return S{l.x+r.x};
}

S e(){
    //単位元
    return S{0};
}

struct F{
    int a;
};

S mapping(F f,S prev){
    //値の更新
    if(f.a==0) return prev;
    return {f.a};
}

F composition(F f,F g){
    //f(g(x)) gに対してfが左から作用する
    if(f.a==0) return g;
    return f;
}

F id(){
    //更新する情報の初期値 単位元に相当する
    return F{0};
}

int main(){
    int n; cin>>n;
    lazysegment seg=lazysegment<S,op,e,F,mapping,composition,id>(n);
    vi a(n);
    map<int,vi> mp;
    rep(i,0,n){
        cin>>a[i];
        mp[a[i]].push_back(i);
    }
    for(auto &[key,value]:mp){
        seg.update(value[0],value[value.size()-1]+1,0,0,seg.x/2,F{key},id());
    }
    rep(i,0,n){
        cout<<seg.qu(i,i+1,0,0,seg.x/2,id()).x<<" ";
    }
    cout<<endl;
}
0