#968574 (C++23) No.318 学学学学学

提出ソース

結果

問題	No.318 学学学学学
ユーザー	ensembleaverage
提出日時	2024-04-02 00:12:14
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	239 ms / 2,000 ms
コード長	4,964 bytes
コンパイル時間	3,458 ms
コンパイル使用メモリ	260,556 KB
実行使用メモリ	16,768 KB
最終ジャッジ日時	2024-04-02 00:12:22
合計ジャッジ時間	7,402 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	14 ms 6,548 KB
testcase_01	AC	29 ms 6,548 KB
testcase_02	AC	37 ms 6,548 KB
testcase_03	AC	23 ms 6,548 KB
testcase_04	AC	36 ms 6,548 KB
testcase_05	AC	239 ms 16,768 KB
testcase_06	AC	176 ms 11,264 KB
testcase_07	AC	150 ms 9,472 KB
testcase_08	AC	133 ms 8,704 KB
testcase_09	AC	115 ms 7,680 KB
testcase_10	AC	95 ms 6,548 KB
testcase_11	AC	206 ms 16,768 KB
testcase_12	AC	145 ms 11,264 KB
testcase_13	AC	128 ms 9,472 KB
testcase_14	AC	115 ms 8,320 KB
testcase_15	AC	101 ms 7,296 KB
testcase_16	AC	87 ms 6,548 KB
testcase_17	AC	119 ms 11,264 KB
testcase_18	AC	112 ms 11,264 KB
testcase_19	AC	120 ms 11,264 KB
testcase_20	AC	68 ms 6,548 KB
testcase_21	AC	1 ms 6,548 KB
testcase_22	AC	2 ms 6,548 KB
testcase_23	AC	2 ms 6,548 KB
testcase_24	AC	2 ms 6,548 KB
testcase_25	AC	2 ms 6,548 KB
testcase_26	AC	2 ms 6,548 KB
testcase_27	AC	2 ms 6,548 KB
testcase_28	AC	2 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード