結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-03-25 20:29:49 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 6,064 bytes |
コンパイル時間 | 2,232 ms |
コンパイル使用メモリ | 165,476 KB |
実行使用メモリ | 10,364 KB |
最終ジャッジ日時 | 2024-11-30 17:09:52 |
合計ジャッジ時間 | 5,171 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>//#include "bits/stdc++.h"using namespace std;typedef long long ll;//#include "boost/multiprecision/cpp_int.hpp"//typedef boost::multiprecision::cpp_int ll;typedef long double dd;//#define i_7 (ll)(1E9+7)#define i_7 998244353#define i_5 i_7-2ll mod(ll a){ll c=a%i_7;if(c>=0)return c;return c+i_7;}typedef pair<ll,ll> l_l;typedef pair<dd,dd> d_d;ll inf=(ll)1E16;#define rep(i,l,r) for(ll i=l;i<=r;i++)#define pb push_backll max(ll a,ll b){if(a<b)return b;else return a;}ll min(ll a,ll b){if(a>b)return b;else return a;}void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);void Min(ll &pos,ll val){pos=min(pos,val);}void Add(ll &pos,ll val){pos=mod(pos+val);}dd EPS=1E-9;#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fi first#define se second#define endl "\n"#define SORT(x) sort(x.begin(),x.end())#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())//template<class T>void max(T a,T b){if(a<b)return b;else return a;}//template<class T>void min(T a,T b){if(a>b)return b;else return a;}//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}////////////////////////////from betrue12 Codeforces 1326Etemplate<typename F, typename T, typename Func_mf, typename Func_op, typename Func_mv>struct LazySegtree {ll n, n_org;vector<T> dat;vector<F> laz;Func_mf merge_functions; //lazyとlazyの演算Func_op operate; //dataとlazyの演算Func_mv merge_values; //dataとdataの演算F fe; //lazyの単位元かつ初期値T te; //dataの単位元かつ初期値LazySegtree(){}LazySegtree(ll n_org,Func_mf merge_functions,Func_op operate,Func_mv merge_values,F fe, T te):n_org(n_org),merge_functions(merge_functions),operate(operate),merge_values(merge_values),fe(fe), te(te){n = 1;while(n < n_org) n <<= 1;dat.resize(2*n-1, te);laz.resize(2*n-1, fe);}void build(vector<T>& A){for(ll k=0; k<ll(A.size()); k++) dat[k+n-1] = A[k];for(ll k=n-2; k>=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]);}void eval(ll k, ll w){if(laz[k] == fe) return;operate(dat[k], laz[k], w);if(k < n-1){merge_functions(laz[2*k+1], laz[k]);merge_functions(laz[2*k+2], laz[k]);}laz[k] = fe;}void update(ll a, ll b, F x){ //[a,b]をupdateupdate(a, b+1, x, 0, 0, n);}void update(ll a, ll b, F x, ll k, ll lb, ll rb){eval(k, rb-lb);if(b <= lb || rb <= a) return;if(a <= lb && rb <= b){merge_functions(laz[k], x);eval(k, rb-lb);}else{ll mb = (lb+rb)>>1;update(a, b, x, 2*k+1, lb, mb);update(a, b, x, 2*k+2, mb, rb);dat[k] = merge_values(dat[2*k+1], dat[2*k+2]);}}T get(ll a, ll b){ //[a,b]から(最小値とか和とかを)getreturn query(a, b+1, 0, 0, n);}T query(ll a, ll b, ll k, ll lb, ll rb){eval(k, rb-lb);if(rb<=a || b<=lb) return te;if(a<=lb && rb<=b) return dat[k];ll mb = (lb+rb)>>1;T vl = query(a, b, 2*k+1, lb, mb);T vr = query(a, b, 2*k+2, mb, rb);return merge_values(vl, vr);}private:};auto make_segtree = [](ll N){ //auto make_segtree = [&](ll N)//区間加算と区間最小/*using F = ll;using T = ll;auto merge_functions = [](F& f, F& g){f += g;};auto operate = [](T& v, F& f, ll w){v += f;};auto merge_values = [](T& a, T& b){return min(a, b);};F fe = 0;T te = inf;*///区間加算と区間最大/*using F = ll;using T = ll;auto merge_functions = [](F& f, F& g){f += g;};auto operate = [](T& v, F& f, ll w){v += f;};auto merge_values = [](T& a, T& b){return max(a, b);};F fe = 0;T te = -inf;*///区間加算と区間和/*using F = ll;using T = ll;auto merge_functions = [](F& f, F& g){f += g;};auto operate = [](T& v, F& f, ll w){v += f*w;};auto merge_values = [](T& a, T& b){return a+b;};F fe = 0;T te = 0;*///区間更新と区間最小using F=ll;using T=ll;auto merge_functions=[](F& f,F& g){f=g;};auto operate = [](T& v, F& f, ll w){v=f;};auto merge_values = [](T& a, T& b){return min(a, b);};F fe = inf;T te = inf;//区間更新と区間最大/*using F=ll;using T=ll;auto merge_functions=[](F& f,F& g){f=g;};auto operate = [](T& v, F& f, ll w){v=f;};auto merge_values = [](T& a, T& b){return max(a, b);};F fe = -inf;T te = -inf;*///区間更新と区間和/*using F=ll;using T=ll;auto merge_functions=[](F& f,F& g){f=g;};auto operate = [](T& v, F& f, ll w){v=f*w;};auto merge_values = [](T& a, T& b){return a+b;};F fe = -inf;T te = 0;*/return LazySegtree<F, T, decltype(merge_functions), decltype(operate), decltype(merge_values)>(N, merge_functions, operate, merge_values, fe, te);};/*auto st = make_segtree(n);vector<ll> init(n);st.build(init);*/int main(){fastioll n;cin>>n;ll a[n];rep(i,0,n-1)cin>>a[i];auto b=make_segtree(n);vector<l_l>v;rep(i,0,n-1){v.pb(l_l(a[i],i));}SORT(v);rep(i,0,n-1){ll l=v[i].se;ll r=v[i].se;while(i+1<=n-1&&v[i].fi==v[i+1].fi){r=v[++i].se;}b.update(l,r,v[i].fi);}rep(i,0,n-1)cout<<b.get(i,i)<<" ";cout<<endl;return 0;}