結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-07-27 05:57:05 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 1,864 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 80,732 KB |
実行使用メモリ | 10,824 KB |
最終ジャッジ日時 | 2024-07-02 10:40:37 |
合計ジャッジ時間 | 4,359 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <deque>#include <queue>#include <algorithm>#include <bitset>#include <tuple>#include <set>#include <map>#define range(i, r) for(int i=0;i<r;i++)#define ranges(i, l, r) for(int i=l;i<r;i++)#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))#define vvi std::vector<std::vector<int> >#define vvl std::vector<std::vector<ll> >#define MODs 1000000007;#define MODn 1000000009;typedef long long int ll;using namespace std;int M=1;std::vector<int> seg;void init(int N){while(N>M)M*=2;M=M*2-1;for(int i=0;i<M;i++) seg.push_back(-1);}void update(int a, int b, int l, int r, int x, int k){if(r<=a||b<=l) return;if(a<=l&&r<=b) {seg[k]=x;return;}update(a, b, l, (l+r)/2, x, k*2+1);update(a, b, (l+r)/2, r, x, k*2+2);}int query(int k, int l, int r, int it, int m){if((M+1)/2-1<=it&&it<=M) return m;if(k<(l+r)/2) return query(k, l, (l+r)/2, it*2+1, max(seg[it],m));return query(k, (l+r)/2, r, it*2+2, max(seg[it],m));}int main(int argc, char const *argv[]) {int N;std::cin >> N;init(N);map<int , pair<int , int> > num;std::vector<int> A(N);for(int i=0;i<N;i++) {std::cin >> A[i];if(num.find(A[i])==num.end()) num.insert(make_pair(A[i], make_pair(i, -1)));else {pair<int,int> p = num.at(A[i]);num.erase(A[i]);num.insert(make_pair(A[i], make_pair(p.first, i)));}}for(int i=0;i<N;i++) seg[i+(M+2)/2-1]=A[i];auto itr = num.begin();for(int i=0;i<num.size();i++) {if((*itr).second.second!=-1) {update((*itr).second.first, (*itr).second.second+1, 0, (M+1)/2, (*itr).first, 0);}itr++;}for(int i=0;i<N;i++) {int ans = query(i, 0, (M+1)/2, 0, -1);if(ans <A[i]) ans = A[i];std::cout << ans << (i==N-1?"\n":" ");}return 0;}