結果
問題 | No.318 学学学学学 |
ユーザー | ふーらくたる |
提出日時 | 2018-01-09 00:01:58 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 4,394 bytes |
コンパイル時間 | 1,189 ms |
コンパイル使用メモリ | 83,672 KB |
実行使用メモリ | 13,932 KB |
最終ジャッジ日時 | 2023-09-04 21:00:47 |
合計ジャッジ時間 | 4,702 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
4,380 KB |
testcase_01 | AC | 23 ms
5,224 KB |
testcase_02 | AC | 28 ms
5,652 KB |
testcase_03 | AC | 18 ms
4,876 KB |
testcase_04 | AC | 26 ms
5,168 KB |
testcase_05 | AC | 208 ms
13,932 KB |
testcase_06 | AC | 150 ms
9,332 KB |
testcase_07 | AC | 110 ms
7,800 KB |
testcase_08 | AC | 85 ms
6,476 KB |
testcase_09 | AC | 64 ms
5,444 KB |
testcase_10 | AC | 42 ms
4,564 KB |
testcase_11 | AC | 212 ms
13,888 KB |
testcase_12 | AC | 109 ms
9,332 KB |
testcase_13 | AC | 81 ms
7,792 KB |
testcase_14 | AC | 59 ms
6,372 KB |
testcase_15 | AC | 44 ms
5,376 KB |
testcase_16 | AC | 28 ms
4,596 KB |
testcase_17 | AC | 90 ms
9,348 KB |
testcase_18 | AC | 71 ms
9,552 KB |
testcase_19 | AC | 88 ms
9,456 KB |
testcase_20 | AC | 25 ms
4,520 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,388 KB |
testcase_24 | AC | 2 ms
4,384 KB |
testcase_25 | AC | 2 ms
4,384 KB |
testcase_26 | AC | 2 ms
4,384 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,380 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; }