結果

問題 No.318 学学学学学
ユーザー 赤信号
提出日時 2024-04-22 17:59:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 233 ms / 2,000 ms
コード長 3,927 bytes
コンパイル時間 4,193 ms
コンパイル使用メモリ 278,548 KB
実行使用メモリ 16,896 KB
最終ジャッジ日時 2024-10-14 17:10:28
合計ジャッジ時間 8,173 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC optimize("O3")
#ifdef LOCAL
#include "algo/debug_ver2.hpp"
#else
#define _debug(...) 42
#endif
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
struct LazySegmentTree {
    int n;
    vector<T> nodes;
    vector<U> lazy;
    vector<int> sizes;
    T ti;
    U ui;
    function<T(T, T)> op;
    function<T(T, U, int)> mapping;
    function<U(U, U)> composition;
    int bit_width(int x) {
        int ret = 0;
        while (x) x >>= 1, ++ret;
        return ret;
    }
    LazySegmentTree(int size, T ti, U ui, function<T(T, T)> op, function<T(T, U, int)> mapping, function<U(U, U)> composition)
        : ti(ti), ui(ui), op(op), mapping(mapping), composition(composition) {
        n = 1;
        while (n < size) n *= 2;
        nodes.resize(n * 2, ti);
        lazy.resize(n * 2, ui);
        sizes.resize(n * 2);
        for (int i = 0; i < size; ++i) sizes[n + i] = 1;
        for (int i = n - 1; i > 0; --i) sizes[i] = sizes[i * 2] + sizes[i * 2 + 1];
    }
    LazySegmentTree(vector<T> vec, T ti, U ui, function<T(T, T)> op, function<T(T, U, int)> mapping, function<U(U, U)> composition)
        : LazySegmentTree(vec.size(), ti, ui, op, mapping, composition) {
        build(vec);
    }
    void build(vector<T> vec) {
        for (int i = 0; i < n; ++i) nodes[n + i] = vec[i];
        for (int i = n - 1; i > 0; --i) update(i);
    }
    void set(int k, T x) {
        k += n;
        for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
        nodes[k] = x;
        for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i);
    }
    T get(int k) {
        k += n;
        for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
        return nodes[k];
    }
    T prod(int l, int r) {
        l += n, r += n;
        for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        T l_cum = ti, r_cum = ti;
        for (; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) l_cum = op(l_cum, nodes[l++]);
            if (r % 2 == 1) r_cum = op(r_cum, nodes[--r]);
        }
        return op(l_cum, r_cum);
    }
    T all_prod() {
        return nodes[1];
    }
    void apply(int k, U x) {
        k += n;
        for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i);
        nodes[k] = mapping(nodes[k], x, sizes[k]);
        for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i);
    }
    void apply(int l, int r, U x) {
        l += n, r += n;
        for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) {
            if (((l >> i) << i) != l) propagate(l >> i);
            if (((r >> i) << i) != r) propagate((r - 1) >> i);
        }
        for (int l2 = l, r2 = r; l2 < r2; l2 /= 2, r2 /= 2) {
            if (l2 % 2 == 1) all_apply(l2++, x);
            if (r2 % 2 == 1) all_apply(--r2, x);
        }
        for (int i = 1; i < bit_width((unsigned int)n); ++i) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
private:
    void update(int x) {
        nodes[x] = op(nodes[x * 2], nodes[x * 2 + 1]);
    }
    void all_apply(int i, U x) {
        nodes[i] = mapping(nodes[i], x, sizes[i]);
        if (i < n) lazy[i] = composition(lazy[i], x);
    }
    void propagate(int i) {
        all_apply(i * 2, lazy[i]);
        all_apply(i * 2 + 1, lazy[i]);
        lazy[i] = ui;
    }
};
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    map<long long, pair<int, int>> pos;
    for (int i = 0; i < n; ++i) {
        if (pos.contains(a[i])) pos[a[i]] = {min(pos[a[i]].first, i), max(pos[a[i]].second, i + 1)};
        else pos[a[i]] = {i, i + 1};
    }
    LazySegmentTree<long long, long long>
        lsgt(a, 0, INT_MIN,
            plus(),
            [](long long x, long long y, int len) { return y == INT_MIN ? x : y * len; },
            [](long long x, long long y) { return y == INT_MIN ? x : y; }
            );
    for (map<long long, pair<int, int>>::iterator it = pos.begin(); it != pos.end(); ++it) lsgt.apply(it -> second.first, it -> second.second, it -> 
        first);
    for (int i = 0; i < n; ++i) cout << (i == 0 ? "" : " ") << lsgt.get(i);
    cout << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0