#858082 (C++17) No.789 範囲の合計

提出ソース

結果

問題	No.789 範囲の合計
ユーザー	sten_san
提出日時	2023-04-09 10:52:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	69 ms / 1,000 ms
コード長	8,834 bytes
コンパイル時間	2,410 ms
コンパイル使用メモリ	204,264 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-15 02:46:45
合計ジャッジ時間	3,387 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	69 ms 6,944 KB
testcase_03	AC	43 ms 6,944 KB
testcase_04	AC	68 ms 6,940 KB
testcase_05	AC	53 ms 6,940 KB
testcase_06	AC	55 ms 6,940 KB
testcase_07	AC	33 ms 6,940 KB
testcase_08	AC	50 ms 6,944 KB
testcase_09	AC	46 ms 6,940 KB
testcase_10	AC	65 ms 6,944 KB
testcase_11	AC	44 ms 6,940 KB
testcase_12	AC	44 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

struct iofast_t {
    iofast_t() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} iofast;

struct uns_t {} uns;
template <typename Element, typename Head, typename ...Args>
auto vec(Element init, Head arg, Args ...args) {
    if constexpr (sizeof...(Args) == 0) return vector(arg, init);
    else return vector(arg, vec(init, args...));
}
template <typename Element, typename Head, typename ...Args>
auto vec(uns_t, Head arg, Args ...args) {
    return vec(Element(), arg, args...);
}

template <typename Container>
auto distance(const Container &c, decltype(begin(c)) iter) {
    return distance(begin(c), iter);
}

template <typename RIter, typename Compare = less<typename iterator_traits<RIter>::value_type>>
auto isort(RIter first, RIter last, Compare comp = Compare()) {
    vector<int> i(distance(first, last));
    iota(begin(i), end(i), 0);
    sort(begin(i), end(i), [&](auto x, auto y) {
        return comp(*(first + x), *(first + y));
    });
    return i;
}

template <typename, template <typename> typename, typename = void_t<>>
struct detect : false_type {};
template <typename T, template <typename> typename Check>
struct detect<T, Check, void_t<Check<T>>> : true_type {};
template <typename T, template <typename> typename Check>
constexpr inline bool detect_v = detect<T, Check>::value;

template <typename T>
using has_member_sort = decltype(declval<T>().sort());

template <typename Container, typename Compare = less<typename Container::value_type>>
auto sorted(Container c, Compare comp = Compare()) {
    if constexpr (detect_v<Container, has_member_sort>) {
        c.sort(comp);
        return c;
    }
    else {
        sort(begin(c), end(c), comp);
        return c;
    }
}

template <typename Container, typename Compare = equal_to<typename Container::value_type>>
auto uniqued(Container c, Compare comp = Compare()) {
    c.erase(unique(begin(c), end(c), comp), end(c));
    return c;
}

template <typename T, typename Compare = less<T>>
T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }
template <typename T, typename Compare = less<T>>
T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }

template <typename F>
constexpr auto fix(F &&f) noexcept {
    return [f = std::tuple<F>(std::forward<F>(f))](auto &&...args) mutable {
        return std::get<0>(f)(fix(std::get<0>(f)), std::forward<decltype(args)>(args)...);
    };
}

template <typename S, S (*Op)(S, S), S (*E)()>
struct dynamic_segment_tree {
    using value_type = S;

    dynamic_segment_tree():
        dynamic_segment_tree(0) {
    }

    dynamic_segment_tree(std::size_t n):
        n_(n), root_(nullptr) {
    }

    ~dynamic_segment_tree() {
        if (root_ != nullptr) delete root_;
    }

public:
    void set(std::size_t i, S x) {
        assert(0 <= i && i < n_);

        update_tree(root_, 0, n_, i, x);
    }

    S get(std::size_t i) const {
        assert(0 <= i && i < n_);

        return get(root_, 0, n_, i);
    }

    S prod(std::size_t l, std::size_t r) const {
        assert(0 <= l && l <= r && r <= n_);

        return prod(root_, 0, n_, l, r);
    }

    S all_prod() const {
        if (root_ != nullptr) {
            return root_->prod;
        }
        return E();
    }

    template <typename F>
    std::size_t max_right(std::size_t l, F &&f) const {
        static_assert(std::is_invocable_r_v<bool, F, S>);

        assert(0 <= l && l <= n_);
        assert(std::forward<F>(f)(E()));

        S acc = E();
        return max_right(root_, 0, n_, l, [&](auto &&x) mutable {
            return std::forward<F>(f)(std::forward<decltype(x)>(x));
        }, acc);
    }

    template <typename F>
    std::size_t min_left(std::size_t r, F &&f) const {
        static_assert(std::is_invocable_r_v<bool, F, S>);

        assert(0 <= r && r <= n_);
        assert(std::forward<F>(f)(E()));

        S acc = E();
        return min_left(root_, 0, n_, r, [&](auto &&x) mutable {
            return std::forward<F>(f)(std::forward<decltype(x)>(x));
        }, acc);
    }

private:
    struct node {
        node(std::size_t i, S value):
            i(i), value(value), prod(value), l(nullptr), r(nullptr) {
        }

        ~node() {
            if (l != nullptr) delete l;
            if (r != nullptr) delete r;
        }

        void update() {
            prod = Op(Op(
                l != nullptr ? l->prod : E(),
                value),
                r != nullptr ? r->prod : E()
            );
        }

        std::size_t i;
        S value, prod;
        node *l, *r;
    };

    static void update_tree(node* &range, std::size_t l, std::size_t r, std::size_t i, S x) {
        using std::swap;

        if (range == nullptr) {
            range = new node(i, x);
            return;
        }

        if (range->i == i) {
            range->value = x;
            range->update();
            return;
        }

        auto m = l + (r - l) / 2;
        if (i < m) {
            if (range->i < i) {
                swap(range->i, i);
                swap(range->value, x);
            }
            update_tree(range->l, l, m, i, x);
        }
        else {
            if (i < range->i) {
                swap(range->i, i);
                swap(range->value, x);
            }
            update_tree(range->r, m, r, i, x);
        }

        range->update();
    }

    static S get(const node *range, std::size_t l, std::size_t r, std::size_t i) {
        if (range == nullptr) {
            return E();
        }

        if (range->i == i) {
            return range->value;
        }

        auto m = l + (r - l) / 2;
        if (i < m) {
            return get(range->l, l, m, i);
        }
        return get(range->r, m, r, i);
    }

    static S prod(const node *range, std::size_t l, std::size_t r, std::size_t query_l, std::size_t query_r) {
        if (range == nullptr || r <= query_l || query_r <= l) {
            return E();
        }

        if (query_l <= l && r <= query_r) {
            return range->prod;
        }

        auto m = l + (r - l) / 2;

        S acc = prod(range->l, l, m, query_l, query_r);
        if (query_l <= range->i && range->i < query_r) {
            acc = Op(acc, range->value);
        }
        return Op(acc, prod(range->r, m, r, query_l, query_r));
    }

    template <typename F>
    static std::size_t max_right(const node *range, std::size_t l, std::size_t r, std::size_t query_l, F f, S &acc) {
        if (range == nullptr || r <= query_l) {
            return r;
        }

        auto m = l + (r - l) / 2;

        auto max_right_l = max_right(range->l, l, m, query_l, f, acc);
        if (max_right_l < m) {
            return max_right_l;
        }

        if (query_l <= range->i) {
            if (S con = Op(acc, range->value); f(con)) {
                acc = con;
            }
            else {
                return range->i;
            }
        }

        if (query_l <= m) {
            if (range->r == nullptr) {
                return r;
            }

            if (S con = Op(acc, range->r->prod); f(con)) {
                acc = con;
                return r;
            }
        }

        return max_right(range->r, m, r, query_l, f, acc);
    }

    template <typename F>
    static std::size_t min_left(const node *range, std::size_t l, std::size_t r, std::size_t query_r, F f, S &acc) {
        if (range == nullptr || query_r <= l) {
            return l;
        }

        auto m = l + (r - l) / 2;

        auto min_left_r = min_left(range->r, m, r, query_r, f, acc);
        if (m < min_left_r) {
            return min_left_r;
        }

        if (range->i < query_r) {
            if (S con = Op(range->value, acc); f(con)) {
                acc = con;
            }
            else {
                return range->i + 1;
            }
        }

        if (m <= query_r) {
            if (range->l == nullptr) {
                return l;
            }

            if (S con = Op(range->l->prod, acc); f(con)) {
                acc = con;
                return l;
            }
        }

        return min_left(range->l, l, m, query_r, f, acc);
    }

private:
    std::size_t n_;
    node *root_;
};

int64_t op(int64_t x, int64_t y) {
    return x + y;
}
int64_t elem() {
    return 0;
}

using segtree = dynamic_segment_tree<int64_t, op, elem>;

int main() {
    constexpr auto lim = 1000000001;

    int n; cin >> n;

    int64_t ans = 0;

    segtree seg(lim);
    while (n--) {
        int t; cin >> t;

        if (t == 0) {
            int x, y; cin >> x >> y;
            seg.set(x, seg.get(x) + y);
        }

        if (t == 1) {
            int l, r; cin >> l >> r; ++r;
            ans += seg.prod(l, r);
        }
    }

    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード