結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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のindexif(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のindexif(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;}