結果
| 問題 | No.318 学学学学学 |
| ユーザー |
 risujiroh
|
| 提出日時 | 2019-01-03 02:50:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 192 ms / 2,000 ms |
| コード長 | 6,258 bytes |
| コンパイル時間 | 2,074 ms |
| コンパイル使用メモリ | 185,544 KB |
| 実行使用メモリ | 17,664 KB |
| 最終ジャッジ日時 | 2024-06-22 18:46:51 |
| 合計ジャッジ時間 | 5,343 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using uint = unsigned int;using lint = long long int;using ulint = unsigned long long int;template<class T = int> using V = vector<T>;template<class T = int> using VV = V< V<T> >;template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }template<class Int> Int rng(Int a, Int b) {static mt19937 mt(chrono::steady_clock().now().time_since_epoch().count());assert(a < b);return uniform_int_distribution<Int>(a, b - 1)(mt);}namespace RandomizedBinarySearchTree {using T = int;T op(const T& lhs, const T& rhs) { return min(lhs, rhs); }T op(const T& lhs, const T& mhs, const T& rhs) { return op(op(lhs, mhs), rhs); }constexpr T e = 2e9;using U = int;constexpr U id = 0;T ap(const U& f, const T& x) { return f != id ? f : x; }U cp(const U& g, const U& f) { return g != id ? g : f; }struct Node;using Tree = Node*;struct Node {int sz = 0;T val = e, acc = e;U laz = id;bool rev = false;Tree cl = nullptr, cr = nullptr;Node() {} // nilNode(const T& val); // leafNode(const T& val, const T& acc, const U& laz, bool rev, Tree cl, Tree cr) :sz(cl->sz + 1 + cr->sz), val(val), acc(acc), laz(laz), rev(rev), cl(cl), cr(cr) {}};Tree nil = new Node();Node::Node(const T& val) : sz(1), val(val), acc(val), cl(nil), cr(nil) {}Tree act(Tree t, const U& f) {if (t == nil) return t;t->val = ap(f, t->val);t->acc = ap(f, t->acc);t->laz = cp(f, t->laz);return t;}Tree reverse(Tree t) {if (t == nil) return t;swap(t->cl, t->cr);t->rev ^= true;return t;}Tree push(Tree t) {if (t->laz == id and !t->rev) return t;if (t->laz != id) {t->cl = act(t->cl, t->laz);t->cr = act(t->cr, t->laz);t->laz = id;}if (t->rev) {t->cl = reverse(t->cl);t->cr = reverse(t->cr);t->rev = false;}return t;}Tree update(Tree t) {t->sz = t->cl->sz + 1 + t->cr->sz;t->acc = op(t->cl->acc, t->val, t->cr->acc);return t;}template<class Itr> Tree build(Itr first, Itr last) {int n = distance(first, last);if (n == 0) return nil;Itr middle = next(first, n / 2);Tree cl = build(first, middle);Tree cr = build(next(middle), last);return new Node(*middle, op(cl->acc, *middle, cr->acc), id, false, cl, cr);}template<class Itr> Itr dump(Tree t, Itr res) {if (t == nil) return res;t = push(t);res = dump(t->cl, res);*res++ = t->val;res = dump(t->cr, res);return res;}Tree rebuild(Tree t) {V<T> v(t->sz);dump(t, begin(v));return build(begin(v), end(v));}Tree merge(Tree tl, Tree tr) {if (tr == nil) return tl;if (tl == nil) return tr;if (rng(0, tl->sz + tr->sz) < tl->sz) {tl = push(tl);tl->cr = merge(tl->cr, tr);return update(tl);} else {tr = push(tr);tr->cl = merge(tl, tr->cl);return update(tr);}}Tree merge(Tree tl, Tree tm, Tree tr) {return merge(merge(tl, tm), tr);}pair<Tree, Tree> split(Tree t, int i) {if (t == nil) return {nil, nil};t = push(t);if (i <= t->cl->sz) {Tree tl;tie(tl, t->cl) = split(t->cl, i);return {tl, update(t)};} else {Tree tr;tie(t->cr, tr) = split(t->cr, i - t->cl->sz - 1);return {update(t), tr};}}tuple<Tree, Tree, Tree> split(Tree t, int l, int r) {Tree tl, tm, tr;tie(tl, tr) = split(t, r);tie(tl, tm) = split(tl, l);return make_tuple(tl, tm, tr);}Tree insert(Tree t, int i, const T& val) {Tree tl, tr;tie(tl, tr) = split(t, i);return merge(tl, new Node(val), tr);}Tree erase(Tree t, int i) {Tree tl, tm, tr;tie(tl, tm, tr) = split(t, i, i + 1);return merge(tl, tr);}T get_val(Tree t, int i) {if (t == nil) return e;if (i == t->cl->sz) return t->val;t = push(t);if (i < t->cl->sz) return get_val(t->cl, i);else return get_val(t->cr, i - t->cl->sz - 1);}Tree set_val(Tree t, int i, const T& val) {if (t == nil) return t;t = push(t);if (i == t->cl->sz) {t->val = val;return update(t);}if (i < t->cl->sz) {t->cl = set_val(t->cl, i, val);return update(t);} else {t->cr = set_val(t->cr, i - t->cl->sz - 1, val);return update(t);}}T acc(Tree t, int l, int r) {if (t == nil or l <= 0 and t->sz <= r) return t->acc;t = push(t);T resl = l < t->cl->sz ? acc(t->cl, l, r) : e;T resr = t->cl->sz + 1 < r ? acc(t->cr, l - t->cl->sz - 1, r - t->cl->sz - 1) : e;T resm = l <= t->cl->sz and t->cl->sz < r ? t->val : e;return op(resl, resm, resr);}Tree act(Tree t, int l, int r, const U& f) {if (t == nil or l <= 0 and t->sz <= r) return act(t, f);t = push(t);if (l < t->cl->sz) t->cl = act(t->cl, l, r, f);if (t->cl->sz + 1 < r) t->cr = act(t->cr, l - t->cl->sz - 1, r - t->cl->sz - 1, f);if (l <= t->cl->sz and t->cl->sz < r) t->val = ap(f, t->val);return update(t);}Tree reverse(Tree t, int l, int r) {Tree tl, tm, tr;tie(tl, tm, tr) = split(t, l, r);tm = reverse(tm);return merge(tl, tm, tr);}int lower_bound(Tree t, const T& val) {if (t == nil) return 0;t = push(t);if (val <= t->val) return lower_bound(t->cl, val);else return t->cl->sz + 1 + lower_bound(t->cr, val);}Tree insert(Tree t, const T& val) {return insert(t, lower_bound(t, val), val);}}using namespace RandomizedBinarySearchTree;int main() {cin.tie(nullptr); ios_base::sync_with_stdio(false);int n; cin >> n;map<int, int> l, r;for (int i = 0; i < n; ++i) {int a; cin >> a;if (!l.count(a)) l[a] = i;r[a] = i;}V<> b(n);Tree t = build(begin(b), end(b));for (const auto& e : l) {t = act(t, e.second, r[e.first] + 1, e.first);}dump(t, begin(b));for (int i = 0; i < n; ++i) {cout << b[i] << (i != n - 1 ? ' ' : '\n');}}