結果
| 問題 | No.318 学学学学学 |
| ユーザー |
 tarakojo1019
|
| 提出日時 | 2021-05-26 14:29:03 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 389 ms / 2,000 ms |
| コード長 | 8,111 bytes |
| コンパイル時間 | 3,380 ms |
| コンパイル使用メモリ | 144,196 KB |
| 最終ジャッジ日時 | 2025-01-21 18:36:05 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cmath>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>//#define ENVIRONMENT_LINKED_ACL#ifdef ENVIRONMENT_LINKED_ACL#include <atcoder/lazysegtree>#endif//#define ENVIRONMENT_LINKED_BOOST#ifdef ENVIRONMENT_LINKED_BOOST#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#endifusing namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;using lpair = std::pair<ll, ll>;#define REP(i, a, b) for (ll i = a; i < b; ++i)#define REPREV(i, a, b) for (ll i = a; i > b; --i)const int _ = []() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(10);return 0;}();template <typename value_t>void resize(value_t& v, const value_t& val) { v = val; }template <typename vec_t, typename value_t, typename... arg_t>void resize(std::vector<vec_t>& v, const value_t& val, int size, arg_t... arg) {v.resize(size);for (auto& c : v) resize(c, val, arg...);}template <typename A, typename B>void chmin(A& a, const B& b) { a = min(a, static_cast<A>(b)); };template <typename A, typename B>void chmax(A& a, const B& b) { a = max(a, static_cast<A>(b)); };//applyは左にかけるtemplate <typename T, typename M>struct lazy_segtree {private:std::function<M(M, M)> composition;std::function<T(M, T)> mapping;std::function<T(T, T)> op;std::function<M()> id;std::function<T()> e;std::vector<M> lazy;std::vector<T> dat;long long size;long long log;void update(int ind) { dat[ind] = op(dat[ind << 1 | 0], dat[ind << 1 | 1]); }void node_apply(int ind, const M& m) {dat[ind] = mapping(m, dat[ind]);if (ind < size) lazy[ind] = composition(m, lazy[ind]);}void prop(int ind) {node_apply(ind << 1 | 0, lazy[ind]);node_apply(ind << 1 | 1, lazy[ind]);lazy[ind] = id();}public:lazy_segtree() : size{0}, log{0} {}lazy_segtree(long long _n, //std::function<T(T, T)> _op, //std::function<T()> _e, //std::function<T(M, T)> _mapping, //std::function<M(M, M)> _composition, //std::function<M()> _id) //: op{_op}, //e{_e}, //mapping{_mapping}, //composition{_composition}, //id{_id} //{size = 1, log = 0;while (size < _n) size <<= 1, ++log;dat.resize(2 * size, e());lazy.resize(2 * size, id());}lazy_segtree(const std::vector<T>& _src, //std::function<T(T, T)> _op, //std::function<T()> _e, //std::function<T(M, T)> _mapping, //std::function<M(M, M)> _composition, //std::function<M()> _id) //: op{_op}, //e{_e}, //mapping{_mapping}, //composition{_composition}, //id{_id} //{size = 1, log = 0;while (size < _src.size()) size <<= 1, ++log;dat.resize(2 * size);lazy.resize(2 * size, id());for (int i = 0; i < _src.size(); ++i) dat[i + size] = _src[i];}//[l,r) mは左にかけるvoid apply(long long l, long long r, const M& m) {assert(0 <= l && l <= r && r <= size);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; --i) {if ((l >> i) << i != l) prop(l >> i);if ((r >> i) << i != r) prop((r - 1) >> i);}long long a = l, b = r;while (a < b) {if (a & 1) node_apply(a++, m);if (b & 1) node_apply(--b, m);a >>= 1, b >>= 1;}for (int i = 1; i <= log; ++i) {if ((l >> i) << i != l) update(l >> i);if ((r >> i) << i != r) update((r - 1) >> i);}}//O(1)T all_prod() { return dat[1]; }//[l,r)T query(long long l, long long r) {assert(0 <= l && l <= r && r <= size);l += size, r += size;for (int i = log; i >= 1; --i) {if ((l >> i) << i != l) prop(l >> i);if ((r >> i) << i != r) prop((r - 1) >> i);}T tmp_l = e();T tmp_r = e();while (l < r) {if (l & 1) tmp_l = op(tmp_l, dat[l++]);if (r & 1) tmp_r = op(dat[--r], tmp_r);l >>= 1, r >>= 1;}return op(tmp_l, tmp_r);}T elem(long long i) {assert(0 <= i && i < size);i += size;for (int j = log; j >= 1; --j) prop(i >> j);return dat[i];}void set(long long i, const T& value) {assert(0 <= i && i < size);i += size;for (int j = log; j >= 1; --j) prop(i >> j);dat[i] = value;for (int j = 1; j <= log; ++j) update(i >> j);}//x <= rで、cond[x-1, r) = falseとなる最大のx 存在しなければ0int search_left(long long r, std::function<bool(T)> cond) {assert(0 <= r && r <= size);assert(cond(e()));if (r == 0) return 0;r += size;for (int j = log; j >= 1; --j) prop((r - 1) >> j);T tmp = e();do {--r;while (r % 2 && r > 1) r >>= 1;T next = op(dat[r], tmp);if (cond(next)) {tmp = next;continue;}while (r < size) {prop(r);r <<= 1;next = op(dat[++r], tmp);if (cond(next)) {--r;tmp = next;}}return r - size + 1;} while ((r & -r) != r);return 0;}//l <= x で、cond(op[l,x+1))=falseとなる最小のx 存在しなければsizeint search_right(long long l, std::function<bool(T)> cond) {assert(0 <= l && l <= size);assert(cond(e()));if (l == size) return size;l += size;T tmp = e();do {while (l % 2 == 0) l >>= 1;T next = op(tmp, dat[l]);if (cond(next)) {++l;tmp = next;continue;}while (l < size) {prop(l);l <<= 1;next = op(tmp, dat[l]);if (cond(next)) {++l;tmp = next;}}return l - size;} while ((l & -l) != l);return size;}};int main() {ll n;cin >> n;vector<ll> A(n);map<ll, lpair> M;REP(i, 0, n) {cin >> A[i];if (M.count(A[i]) == 0) M[A[i]] = {i, i};chmax(M[A[i]].second, i);}lazy_segtree<ll, ll> seg{n, [](ll a, ll b) { return a; }, []() { return 0; }, [](ll m, ll a) { return m ? m : a; }, [](ll m1, ll m2) { return m1? m1 : m2; }, []() { return 0; }};for (auto [a, range] : M) {seg.apply(range.first, range.second + 1, a);}REP(i, 0, n) {cout << seg.elem(i);if (i == n - 1) {cout << endl;}else {cout << " ";}}return 0;}