結果

問題 No.318 学学学学学
ユーザー pekempeypekempey
提出日時 2016-02-29 01:14:11
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 572 ms / 2,000 ms
コード長 3,291 bytes
コンパイル時間 3,381 ms
コンパイル使用メモリ 185,652 KB
実行使用メモリ 17,656 KB
最終ジャッジ日時 2023-09-04 18:35:17
合計ジャッジ時間 11,458 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
4,712 KB
testcase_01 AC 77 ms
5,996 KB
testcase_02 AC 92 ms
6,528 KB
testcase_03 AC 60 ms
5,576 KB
testcase_04 AC 83 ms
6,200 KB
testcase_05 AC 553 ms
17,656 KB
testcase_06 AC 457 ms
12,868 KB
testcase_07 AC 414 ms
11,300 KB
testcase_08 AC 369 ms
10,056 KB
testcase_09 AC 321 ms
9,128 KB
testcase_10 AC 289 ms
8,412 KB
testcase_11 AC 572 ms
17,556 KB
testcase_12 AC 443 ms
12,908 KB
testcase_13 AC 393 ms
11,420 KB
testcase_14 AC 333 ms
10,064 KB
testcase_15 AC 297 ms
9,436 KB
testcase_16 AC 276 ms
8,400 KB
testcase_17 AC 401 ms
12,804 KB
testcase_18 AC 370 ms
12,928 KB
testcase_19 AC 380 ms
12,868 KB
testcase_20 AC 272 ms
8,344 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
typedef long long ll;

const int inf = 1e9;

struct RBST {
	struct node {
		int val, size;
		node *lch, *rch;
		int mx;
		int lazy;
		node(int val) : val(val), mx(val), size(1), lch(0), rch(0), lazy(-1) {}
	};
	node *root;
	RBST(int n) {
		root = build(0, n);
	}
	node *build(int l, int r) {
		if (r - l == 1) return new node(0);
		return merge(build(l, (l + r) / 2), build((l + r) / 2, r));
	}

	unsigned xor32() {
		static unsigned z = time(NULL);
		z ^= z << 13; z ^= z >> 17; z ^= z << 5;
		return z;
	}
	int size(node *x) {
		return x ? x->size : 0;
	}
	int mx(node *x) {
		return x ? x->mx : -inf;
	}
	node *push(node *x) {
		x->size = 1 + size(x->lch) + size(x->rch);
		if (x->lazy != -1) {
			x->val = x->lazy;
			if (x->lch) x->lch->lazy = x->lazy;
			if (x->rch) x->rch->lazy = x->lazy;
			x->lazy = -1;
		}
		x->mx = max({ x->val, mx(x->lch), mx(x->rch) });
		return x;
	}
	node *merge(node *x, node *y) {
		if (!x) return y;
		if (!y) return x;
		if (xor32() % (size(x) + size(y)) < size(x)) {
			x = push(x);
			x->rch = merge(x->rch, y);
			return push(x);
		} else {
			y = push(y);
			y->lch = merge(x, y->lch);
			return push(y);
		}
	}
	pair<node *, node *> split(node *x, int k) {
		if (!x) return{ 0, 0 };
		x = push(x);
		if (size(x->lch) >= k) {
			auto p = split(x->lch, k);
			x->lch = p.second;
			return{ p.first, push(x) };
		} else {
			auto p = split(x->rch, k - size(x->lch) - 1);
			x->rch = p.first;
			return{ push(x), p.second };
		}
	}
	node *insert(node *x, int k, int v) {
		auto p = split(x, k);
		node *n = new node(v);
		return merge(p.first, merge(n, p.second));
	}
	node *erase(node *x, int k) {
		auto p = split(x, k);
		return merge(p.first, split(p.second, 1).second);
	}
	void push_back(int v) {
		root = merge(root, new node(v));
	}
	int lower_bound(node *x, int v) {
		if (!x) return 0;
		if (v < x->val) return lower_bound(x->lch, v);
		return lower_bound(x->rch, v) + size(x->lch) + 1;
	}
	node *at(node *x, int k) {
		if (size(x->lch) == k) return x;
		if (size(x->lch) > k) return at(x->lch, k);
		return at(x->rch, k - size(x->lch) - 1);
	}

	void update(int a, int b, int v) {
		auto x = split(root, b);
		auto y = split(x.first, a);
		y.second->lazy = v;
		root = merge(merge(y.first, y.second), x.second);
	}

	int query(int a, int b) {
		auto x = split(root, b);
		auto y = split(x.first, a);
		ll ret = mx(y.second);
		root = merge(merge(y.first, y.second), x.second);
		return ret;
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) scanf("%d", &a[i]);
	map<int, int> first, last;
	repr(i, n) first[a[i]] = i;
	rep(i, n) last[a[i]] = i;
	RBST tr(n);

	rep(i, n) tr.update(i, i + 1, a[i]);
	for (auto kv : first) if (last.count(kv.first)) {
		tr.update(kv.second, last[kv.first] + 1, kv.first);
	}

	rep(i, n) printf("%d ", (int)tr.query(i, i + 1));
	cout << endl;
	return 0;
}
0