結果

問題 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](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;
}
0