結果

問題 No.318 学学学学学
ユーザー Shibuyap
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 2147483647
int 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](z1-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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0