結果

問題 No.318 学学学学学
ユーザー ShibuyapShibuyap
提出日時 2021-02-19 19:29:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 363 ms / 2,000 ms
コード長 3,446 bytes
コンパイル時間 2,346 ms
コンパイル使用メモリ 215,492 KB
実行使用メモリ 188,252 KB
最終ジャッジ日時 2024-09-16 15:37:35
合計ジャッジ時間 9,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
30,208 KB
testcase_01 AC 63 ms
45,696 KB
testcase_02 AC 73 ms
51,696 KB
testcase_03 AC 53 ms
39,808 KB
testcase_04 AC 66 ms
47,104 KB
testcase_05 AC 352 ms
188,252 KB
testcase_06 AC 294 ms
183,584 KB
testcase_07 AC 261 ms
175,968 KB
testcase_08 AC 226 ms
151,212 KB
testcase_09 AC 171 ms
98,648 KB
testcase_10 AC 95 ms
25,948 KB
testcase_11 AC 363 ms
188,252 KB
testcase_12 AC 295 ms
182,048 KB
testcase_13 AC 267 ms
173,668 KB
testcase_14 AC 237 ms
159,272 KB
testcase_15 AC 200 ms
136,532 KB
testcase_16 AC 111 ms
55,520 KB
testcase_17 AC 260 ms
184,356 KB
testcase_18 AC 230 ms
184,348 KB
testcase_19 AC 222 ms
184,352 KB
testcase_20 AC 85 ms
41,956 KB
testcase_21 AC 13 ms
15,616 KB
testcase_22 AC 13 ms
15,744 KB
testcase_23 AC 13 ms
15,744 KB
testcase_24 AC 13 ms
15,744 KB
testcase_25 AC 13 ms
15,616 KB
testcase_26 AC 13 ms
15,744 KB
testcase_27 AC 12 ms
15,744 KB
testcase_28 AC 13 ms
15,744 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