結果

問題 No.3134 二分探索木
コンテスト
ユーザー ID 21712
提出日時 2025-05-02 13:09:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 225 ms / 2,000 ms
コード長 933 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 75,956 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2025-05-02 13:09:12
合計ジャッジ時間 4,708 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {

	int N;
	vector<int> A;

	cin >> N;
	
	int id = 1;
	map<int,int> m;

	vector<int> B(N), C(N);
	
	C[0] = N - 1;
	
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		auto ub = m.upper_bound(a);
		auto lb = m.upper_bound(a);
		if (lb == m.begin()) {
			lb = m.end();
		} else if (m.size() > 0) {
			lb--;
		}
		if (lb == m.end()) {
			if (ub != m.end()) {
				B[i] = B[ub->second] + 1;
				C[i] = (ub->first - 1) - 1;
			}
		} else if (ub == m.end()) {
			B[i] = B[lb->second] + 1;
			C[i] = N - (lb->first + 1);
		} else {
			B[i] = max(B[lb->second], B[ub->second]) + 1;
			C[i] = (ub->first - 1) - (lb->first + 1);
		}
		m.emplace(a, i);
	}

	for (int i = 0; i < N; i++) {
		if (i > 0) cout << " ";
		cout << B[i];
	}
	cout << endl;
	
	for (int i = 0; i < N; i++) {
		if (i > 0) cout << " ";
		cout << C[i];
	}
	cout << endl;
	
	return 0;
}
0