結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2021-02-19 19:29:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 495 ms / 2,000 ms |
コード長 | 3,446 bytes |
コンパイル時間 | 2,530 ms |
コンパイル使用メモリ | 207,632 KB |
最終ジャッジ日時 | 2025-01-18 23:05:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)#define srep(i,s,t) for (int i = s; i < t; ++i)using namespace std;typedef pair<int,int> P;typedef long long int ll;#define yn {puts("Yes");}else{puts("No");}const int MAX_N = 1 << 19;#define NUM 2147483647int nn = 1;int data_[MAX_N][210];void init(int first_N){nn = 1;if(first_N < 10) nn = 100;while(nn < first_N)nn *= 2;}// [left,right]の区間の値をvalueに更新する// update_(left,right,value,0,0,nn-1,mm)のように呼ぶvoid update_(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right, int mm){if(update_right < node_left || update_left > node_right)return;else if(update_left <= node_left && update_right >= node_right){data_[node_id][mm] = new_value;}else{if(data_[node_id][mm] >= 0){data_[2*node_id+1][mm] = data_[node_id][mm];data_[2*node_id+2][mm] = data_[node_id][mm];data_[node_id][mm] = -1;}update_(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2,mm);update_(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right,mm);}}// [left,right]の区間の値をvalueに更新する// update(left,right,value,mm)のように呼ぶvoid update(int left, int right, int value, int mm){update_(left,right,value,0,0,nn-1,mm);}// query_(ite,ite,0,0,nn-1,mm)のように呼ぶint query_(int search_left,int search_right,int node_id,int node_left,int node_right,int mm){if(search_right < node_left || search_left > node_right){return -1;}else if(node_left <= search_left && node_right >= search_right && data_[node_id][mm] >= 0){return data_[node_id][mm];}else{int left = query_(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,mm);int right = query_(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,mm);return max(left,right);}}// query(ite,mm)のように呼ぶint query(int ite, int mm){return query_(ite,ite,0,0,nn-1,mm);}// 座標圧縮 a[n] -> z[n](zは1-index)vector<int> zaatsu(const vector<int>& a){int n = a.size();vector<int> b, pre_b, z;rep(i,n)pre_b.push_back(a[i]);sort(pre_b.begin(), pre_b.end());rep(i,n){if(i == 0){b.push_back(pre_b[i]);}else{if(pre_b[i] != pre_b[i-1]){b.push_back(pre_b[i]);}}}rep(i,n){int tmp_z = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;z.push_back(tmp_z);}return z;}vector<int> v[MAX_N];int main() {int n;cin >> n;init(n+100);vector<int> a(n);rep(i,n) cin >> a[i];vector<int> z = zaatsu(a);map<int,int> mp;rep(i,n) mp[z[i]] = a[i];rep(i,n){v[z[i]].push_back(i);}srep(i,1,MAX_N){vector<int> keep;rep(j,v[i].size()){keep.push_back(v[i][j]);/*if(query(v[i][j],0) == 0){keep.push_back(v[i][j]);}*/}if(keep.size() == 0) continue;int left = keep[0];int right = keep[keep.size()-1];update(left,right,i,0);}rep(i,n){cout << mp[query(i,0)];if(i == n-1) cout << endl;else cout << ' ';}return 0;}