結果

問題 No.318 学学学学学
ユーザー pekempeypekempey
提出日時 2016-02-29 01:05:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 557 ms / 2,000 ms
コード長 3,165 bytes
コンパイル時間 2,010 ms
コンパイル使用メモリ 174,992 KB
実行使用メモリ 17,920 KB
最終ジャッジ日時 2024-06-22 16:23:13
合計ジャッジ時間 10,237 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
6,812 KB
testcase_01 AC 79 ms
6,816 KB
testcase_02 AC 95 ms
6,940 KB
testcase_03 AC 60 ms
6,944 KB
testcase_04 AC 81 ms
6,940 KB
testcase_05 AC 547 ms
17,920 KB
testcase_06 AC 472 ms
13,184 KB
testcase_07 AC 407 ms
11,648 KB
testcase_08 AC 366 ms
10,368 KB
testcase_09 AC 327 ms
9,600 KB
testcase_10 AC 287 ms
8,704 KB
testcase_11 AC 557 ms
17,920 KB
testcase_12 AC 421 ms
13,184 KB
testcase_13 AC 372 ms
11,648 KB
testcase_14 AC 346 ms
10,496 KB
testcase_15 AC 300 ms
9,472 KB
testcase_16 AC 274 ms
8,704 KB
testcase_17 AC 407 ms
13,056 KB
testcase_18 AC 363 ms
13,184 KB
testcase_19 AC 403 ms
13,184 KB
testcase_20 AC 282 ms
8,704 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:114:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  114 |         rep(i, n) scanf("%d", &a[i]);
      |                   ~~~~~^~~~~~~~~~~~~

ソースコード

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() : root(0) {}
	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;
	rep(i, n) tr.push_back(0);

	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