#660542 (C++17) No.318 学学学学学

提出ソース
結果

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

raw source code
#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>
#endif

using 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   存在しなければ0
    int 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  存在しなければsize
    int 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;
}
yukicoder

結果

ソースコード
