結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2018-11-15 11:44:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 1,746 bytes |
コンパイル時間 | 930 ms |
コンパイル使用メモリ | 100,664 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2024-06-22 18:45:48 |
合計ジャッジ時間 | 4,889 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <unordered_map>#include <unordered_set>#include <random>using namespace std;typedef long long int ll;typedef pair<int, int> P;const int MAX_N=1<<17;int ans[2*MAX_N-1], part[2*MAX_N-1];int m;void init(int n){m=1;while(m<n) m*=2;for(int i=0; i<2*m-1; i++){ans[i]=0;part[i]=0;}}void eval(int k, int l, int r){if(part[k]>0){ans[k]=part[k];if(k<m-1){part[2*k+1]=part[k];part[2*k+2]=part[k];}part[k]=0;}}void update(int a, int b, int x, int k, int l, int r){eval(k, l, r);if(r<=a || b<=l) return;if(a<=l && r<=b){part[k]=x;eval(k, l, r);}else{update(a, b, x, k*2+1, l, (l+r)/2);update(a, b, x, k*2+2, (l+r)/2, r);ans[k]=max(ans[2*k+1], ans[2*k+2]);}}int find(int a, int b, int k, int l, int r){eval(k, l, r);if(b<=l || r<=a){return 0;}if(a<=l && r<=b){return ans[k];}else{return max(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r));}}int main(){int n;cin>>n;map<int, int> mn, mx;for(int i=0; i<n; i++){int a;cin>>a;if(mn.find(a)==mn.end()){mn[a]=i;mx[a]=i;}else{mn[a]=min(i, mn[a]);mx[a]=max(i, mx[a]);}}init(n);for(auto p:mn){int a=p.first, i1=p.second, i2=mx[a];update(i1, i2+1, a, 0, 0, m);}for(int i=0; i<n; i++){cout<<find(i, i+1, 0, 0, m);if(i<n-1) cout<<" ";}cout<<endl;return 0;}