結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2020-03-01 04:52:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 1,906 bytes |
コンパイル時間 | 1,049 ms |
コンパイル使用メモリ | 89,632 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 20:28:54 |
合計ジャッジ時間 | 5,775 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
main.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 73 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;#include<vector>#include<functional>template<typename T>struct dualsegtree{using F=function<T(T,T)>;const F lazycalcfn,updatefn;int n;T lazydefvalue;vector<T>dat,lazy;vector<bool>lazyflag;dualsegtree(int n_=0,T defvalue=0,const F lazycalcfn_=[](T a,T b){return a+b;},const F updatefn_=[](T a,T b){return a+b;},T lazydefvalue_=0):lazydefvalue(lazydefvalue_),lazycalcfn(lazycalcfn_),updatefn(updatefn_){n=1;while(n<n_)n<<=1;dat.assign(n,defvalue);lazy.assign(n-1,lazydefvalue);lazyflag.assign(n-1,false);}void copy(const vector<T>&v){for(int i=0;i<v.size();i++)dat[i]=v[i];lazy.assign(n-1,lazydefvalue);lazyflag.assign(n-1,false);}void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b){if(r<0)r=n;if(b<=l||r<=a)return;else if(a<=l&&r<=b){if(k<n-1){lazy[k]=lazycalcfn(lazy[k],x);lazyflag[k]=true;}else dat[k-n+1]=updatefn(dat[k-n+1],x);}else{if(lazyflag[k]){update(0,n,lazy[k],k*2+1,l,(l+r)/2);update(0,n,lazy[k],k*2+2,(l+r)/2,r);lazy[k]=lazydefvalue;lazyflag[k]=false;}update(a,b,x,k*2+1,l,(l+r)/2);update(a,b,x,k*2+2,(l+r)/2,r);}}T query(int i){T ret=dat[i];i+=n-1;while(i>0){i=(i-1)/2;if(lazyflag[i])ret=updatefn(ret,lazy[i]);}return ret;}};int N;main(){cin>>N;dualsegtree<int>P(N,0,[](int a,int b){return b;},[](int a,int b){return b;});vector<pair<int,int> >A(N);for(int i=0;i<N;i++){cin>>A[i].first;A[i].second=i;}sort(A.begin(),A.end());for(int i=0;i<A.size();){P.update(A[i].second,A[i].second+1,A[i].first);i++;while(i<A.size()&&A[i-1].first==A[i].first){P.update(A[i-1].second,A[i].second+1,A[i].first);i++;}}for(int i=0;i<N;i++)cout<<P.query(i)<<(i+1==N?"\n":" ");}