結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2018-07-27 21:45:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 1,027 ms |
コンパイル使用メモリ | 87,932 KB |
実行使用メモリ | 10,196 KB |
最終ジャッジ日時 | 2024-06-22 18:37:20 |
合計ジャッジ時間 | 3,862 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <map>#include <cstdio>using namespace std;int seg[1<<18],n;void up(int a,int b,int r,int l,int k,int x){if(b<r||l<a)return;if(a<=r&&l<=b)seg[k]=max(seg[k],x);else{up(a,b,r,(r+l-1)/2,k*2+1,x);up(a,b,(r+l+1)/2,l,k*2+2,x);}}vector<int>com;map<int,int>p;int s[100005],t[100005],q[100005];int main(void){cin>>n;for(int i=0;i<n;i++){s[i]=100000;scanf("%d",q+i);com.push_back(q[i]);}sort(com.begin(),com.end());com.erase(unique(com.begin(),com.end()),com.end());for(int i=0;i<com.size();i++)p[com[i]]=i;for(int i=0;i<n;i++){q[i]=p[q[i]];s[q[i]]=min(s[q[i]],i);t[q[i]]=max(t[q[i]],i);}for(int i=0;i<com.size();i++){up(s[i],t[i],0,(1<<17)-1,0,i);}for(int i=0;i<n;i++){int j=i+(1<<17)-1,ans=seg[j];while(j>0){j=(j-1)/2;ans=max(ans,seg[j]);}printf("%d",com[ans]);if(i!=n-1)printf(" ");}printf("\n");}