結果

問題 No.318 学学学学学
ユーザー ShibuyapShibuyap
提出日時 2021-02-19 19:29:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 307 ms / 2,000 ms
コード長 3,446 bytes
コンパイル時間 2,502 ms
コンパイル使用メモリ 213,832 KB
実行使用メモリ 194,492 KB
最終ジャッジ日時 2023-10-14 21:56:16
合計ジャッジ時間 9,884 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
34,716 KB
testcase_01 AC 49 ms
56,224 KB
testcase_02 AC 57 ms
58,328 KB
testcase_03 AC 39 ms
43,428 KB
testcase_04 AC 51 ms
56,016 KB
testcase_05 AC 307 ms
190,528 KB
testcase_06 AC 273 ms
185,588 KB
testcase_07 AC 183 ms
180,552 KB
testcase_08 AC 160 ms
158,144 KB
testcase_09 AC 140 ms
106,556 KB
testcase_10 AC 89 ms
61,900 KB
testcase_11 AC 280 ms
189,600 KB
testcase_12 AC 210 ms
194,256 KB
testcase_13 AC 186 ms
193,000 KB
testcase_14 AC 165 ms
192,284 KB
testcase_15 AC 143 ms
191,572 KB
testcase_16 AC 109 ms
190,784 KB
testcase_17 AC 178 ms
194,312 KB
testcase_18 AC 148 ms
194,080 KB
testcase_19 AC 139 ms
194,492 KB
testcase_20 AC 96 ms
191,036 KB
testcase_21 AC 9 ms
17,668 KB
testcase_22 AC 9 ms
17,612 KB
testcase_23 AC 8 ms
17,856 KB
testcase_24 AC 8 ms
17,724 KB
testcase_25 AC 9 ms
17,764 KB
testcase_26 AC 9 ms
17,700 KB
testcase_27 AC 8 ms
17,708 KB
testcase_28 AC 8 ms
17,672 KB
権限があれば一括ダウンロードができます

ソースコード

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