結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2018-01-09 00:01:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 4,394 bytes |
コンパイル時間 | 956 ms |
コンパイル使用メモリ | 83,940 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-06-22 18:30:13 |
合計ジャッジ時間 | 3,714 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <limits>#include <map>using namespace std;struct RUQ_SET {using T = int;static inline constexpr T identity() { return std::numeric_limits<int>::max(); }// static inline T op(const T& a, const T& b) { return a + b; }};template <class Object>struct RUQ_OP {using T = typename Object::T;using M = T;static inline constexpr M identity() { return -1; }static inline M op(const M& a, const M& b) { return (b == identity()) ? a : b; }// mpをaに適用するstatic inline T apply(const M& mp, const int a, int w) { return (mp == identity()) ? a : T(mp); }};// 区間更新一点取得template <class Object, class Operator>class LazyPropagationSegmentTree {const int N;const int h;using T = typename Object::T;using M = typename Operator::M;std::vector<T> t;std::vector<M> lazy;inline int lowest_pow_of_2(int n) {int res = 1;while (res < n) res <<= 1;return res;}// log2_X <= nを満たす最大のXを計算inline int log2(int n) {int res = 0;while (n >> (res + 1)) res++;return res;}inline void prop_to(int i) {t[i] = Object::op(t[2 * i], t[2 * i + 1]);}inline void eval(int i, int w) {if (i < N and lazy[i] != Operator::identity()) {t[i] = Operator::apply(lazy[i], t[i], w);if (2 * i < N) {// 伝搬lazy[2 * i] = Operator::op(lazy[2 * i], lazy[i]);lazy[2 * i + 1] = Operator::op(lazy[2 * i + 1], lazy[i]);} else if (i < N) {t[2 * i] = Operator::apply(lazy[i], t[2 * i], w / 2);t[2 * i + 1] = Operator::apply(lazy[i], t[2 * i + 1], w / 2);}lazy[i] = Operator::identity();}}public:LazyPropagationSegmentTree(int n): N(lowest_pow_of_2(n)), h(log2(N) + 1),t(2 * N, Object::identity()), lazy(N, Operator::identity()) { }template <class InputIt>LazyPropagationSegmentTree(InputIt first, InputIt last): N(lowest_pow_of_2(std::distance(first, last))),h(log2(N) + 1),t(2 * N, Object::identity()),lazy(N, Operator::identity()) {std::copy(first, last, t + N);for (int i = N - 1; i > 0; i--) prop_to(i);}inline void update(int l, int r, M mp) {update(l, r, mp, 1, 0, N);}inline void update(int l, int r, M mp, int id, int nodel, int noder) {// 範囲外eval(id, noder - nodel); // 演算の順序を守るためさきに伝播させるif (noder <= l or r <= nodel) return;if (id >= N) { // 葉t[id] = Operator::apply(mp, t[id], 1);return;}if (l <= nodel and noder <= r) {lazy[id] = Operator::op(lazy[id], mp);eval(id, noder - nodel);} else {update(l, r, mp, 2 * id, nodel, (nodel + noder) / 2);update(l, r, mp, 2 * id + 1, (nodel + noder) / 2, noder);// t[id] = Object::op(t[2 * id], t[2 * id + 1]);}}T get(int i) {i += N;for (int j = (h - 1); j > 0; j--) eval(i >> j, 1 << j);return t[i];}/*T query(int l, int r) {return query(l, r, 1, 0, N);}T query(int l, int r, int id, int nodel, int noder) {// 範囲外eval(id, noder - nodel);if (noder <= l or r <= nodel) return Object::identity();// 完全に含まれるif (l <= nodel and noder <= r) return t[id];T resl = query(l, r, 2 * id, nodel, (nodel + noder) / 2);T resr = query(l, r, 2 * id + 1, (nodel + noder) / 2, noder);return Object::op(resl, resr);}*/};int main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;map<int, int> left, right;for (int i = 0; i < N; i++) {int a;cin >> a;if (left.count(a) == 0) left[a] = i;right[a] = i;}LazyPropagationSegmentTree<RUQ_SET, RUQ_OP<RUQ_SET>> segtree(N);for (auto p : left) segtree.update(p.second, right[p.first] + 1, p.first);for (int i = 0; i < N; i++) {cout << segtree.get(i) << " ";}cout << endl;return 0;}