結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2018-01-09 00:01:58 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
6,812 KB |
testcase_01 | AC | 20 ms
6,940 KB |
testcase_02 | AC | 24 ms
6,944 KB |
testcase_03 | AC | 16 ms
6,940 KB |
testcase_04 | AC | 21 ms
6,940 KB |
testcase_05 | AC | 140 ms
14,208 KB |
testcase_06 | AC | 113 ms
9,472 KB |
testcase_07 | AC | 87 ms
7,936 KB |
testcase_08 | AC | 70 ms
6,940 KB |
testcase_09 | AC | 55 ms
6,940 KB |
testcase_10 | AC | 37 ms
6,944 KB |
testcase_11 | AC | 148 ms
14,208 KB |
testcase_12 | AC | 93 ms
9,472 KB |
testcase_13 | AC | 69 ms
7,808 KB |
testcase_14 | AC | 49 ms
6,944 KB |
testcase_15 | AC | 36 ms
6,944 KB |
testcase_16 | AC | 26 ms
6,940 KB |
testcase_17 | AC | 77 ms
9,344 KB |
testcase_18 | AC | 61 ms
9,472 KB |
testcase_19 | AC | 74 ms
9,472 KB |
testcase_20 | AC | 23 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,944 KB |
testcase_24 | AC | 1 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 1 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,940 KB |
ソースコード
#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; }