結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-12-20 13:22:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 200 ms / 2,000 ms |
コード長 | 2,048 bytes |
コンパイル時間 | 3,079 ms |
コンパイル使用メモリ | 205,844 KB |
最終ジャッジ日時 | 2025-01-08 13:29:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>using namespace std;template<class T>struct lazy_segment_tree{int n;vector<T> dat,lazy;T de,le;T f(T a,T b){return a+b;}void g(T& a,T b){a = b;}void h(T& a,T b){a = b;}lazy_segment_tree(){}lazy_segment_tree(int sz){n = 1;while(n<=sz)n<<=1;de = 0;le = 0;dat.resize(2*n-1,de);lazy.resize(2*n-1,le);}lazy_segment_tree(vector<T> const& v){int sz = v.size();n = 1;while(n<=sz)n<<=1;de = 0;le = 0;dat.resize(2*n-1,de);lazy.resize(2*n-1,le);for(int i=0;i<sz;++i){dat[i+n-1] = v[i];}for(int i=n-2;i>=0;--i){dat[i] = f(dat[i*2+1],dat[i*2+2]);}}void eval(int k,int l,int r){if(lazy[k]!=le){g(dat[k],lazy[k]);if(r-l>1){h(lazy[2*k+1],lazy[k]);h(lazy[2*k+2],lazy[k]);}lazy[k] = le;}}void update(int a,int b,T x,int k=0,int l=0,int r=-1){if(r<0)r=n;eval(k,l,r);if(b<=l||r<=a)return;if(a<=l&&r<=b){h(lazy[k],x);eval(k,l,r);}else{update(a,b,x,2*k+1,l,(r+l)/2);update(a,b,x,2*k+2,(r+l)/2,r);dat[k] = f(dat[2*k+1],dat[2*k+2]);}}T query(int a,int b,int k=0,int l=0,int r=-1){if(r<0)r=n;if(b<=l||r<=a)return de;eval(k,l,r);if(a<=l&&r<=b)return dat[k];T vl = query(a,b,2*k+1,l,(r+l)/2);T vr = query(a,b,2*k+2,(r+l)/2,r);return f(vl,vr);}T operator[](int k){return query(k,k+1);}};void yukico318(){int n;cin>>n;vector<int> a(n);for(auto& ai:a)cin>>ai;struct section{int l,r;section():r(-1),l((1LL<<28)){}void operator()(int k){if(l>k)l=k;if(r<k)r=k;}};map<int,section> mp;for(int i=0;i<n;++i){mp[a[i]](i);}lazy_segment_tree<int> seg(n);for(auto const& sec:mp){seg.update(sec.second.l,sec.second.r+1,sec.first);}for(int i=0;i<n;++i){cout<<seg[i]<<" ";}cout<<endl;}int main(){yukico318();}