結果
問題 | 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"); }