結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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; }
// mpa
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 <= nX
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0