結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2020-07-08 17:24:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 2,390 bytes |
コンパイル時間 | 1,585 ms |
コンパイル使用メモリ | 180,056 KB |
実行使用メモリ | 15,696 KB |
最終ジャッジ日時 | 2024-10-04 06:22:43 |
合計ジャッジ時間 | 6,201 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> P;typedef pair<ll,ll> l_l;typedef vector<int> vi;typedef vector<ll> vl;typedef vector<P> vp;typedef vector<l_l> vpl;typedef vector<string> vs;typedef pair<l_l,ll> lll;#define pb push_back#define sz(x) (int)(x).size()#define fi first#define se second#define rep(i,n) for(int i=0;i<(n);i++)#define rrep(i,n) for(int i=1;i<=(n);i++)const int INF=1001001000;const int mINF=-1001001000;const ll LINF=10100100100100100;const ll dx[4]={1,-1,0,0};const ll dy[4]={0,0,1,-1};template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}ll n,N;vl a,node,lazy;void init(){N=1;while(N<n)N*=2;node.resize(2*N-1,0);lazy.resize(2*N-1,0);}void eval(ll l,ll r,ll pos){if(lazy[pos]!=0){node[pos]=max(node[pos],lazy[pos]);if(r-l>1){lazy[2*pos+1]=lazy[pos];lazy[2*pos+2]=lazy[pos];}lazy[pos]=0;}}void add(ll l,ll r,ll val,ll bottom=0,ll top=-1,ll pos=0){if(top<0)top=N;//cout<<pos<<endl;eval(bottom,top,pos);if(r<=bottom||top<=l)return;if(l<=bottom&&top<=r){lazy[pos]=max(val,lazy[pos]);eval(bottom,top,pos);}else{ll mid=(bottom+top)/2;add(l,r,val,bottom,mid,2*pos+1);add(l,r,val,mid,top,2*pos+2);node[pos]=max(node[2*pos+1],node[2*pos+2]);}}ll getmax(ll l,ll r,ll bottom=0,ll top=-1,ll pos=0){if(top<0)top=N;eval(bottom,top,pos);if(r<=bottom||top<=l)return 0;if(l<=bottom&&top<=r)return node[pos];ll mid=(bottom+top)/2;ll vl=getmax(l,r,bottom,mid,2*pos+1);ll vr=getmax(l,r,mid,top,2*pos+2);return max(vl,vr);}int main(){cin>>n;init();a.resize(n,0);rep(i,n)cin>>a[i];map<ll,l_l> mp;rep(i,n){if(mp[a[i]].fi==0&&mp[a[i]].se==0){//cout<<a[i]<<" "<<i<<endl;mp[a[i]]={i+1,i+1};}else{mp[a[i]].se=i+1;}}for(auto p:mp){//cout<<p.fi<<" "<<p.se.fi<<" "<<p.se.se<<endl;add(p.se.fi-1,p.se.se,p.fi);}vl b;rep(i,n)b.pb(getmax(i,i+1));for(auto bb:b)cout<<bb<<" ";cout<<endl;return 0;}