結果
問題 | No.789 範囲の合計 |
ユーザー | AC2K |
提出日時 | 2023-10-22 18:10:31 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 152 ms / 1,000 ms |
コード長 | 8,358 bytes |
コンパイル時間 | 1,188 ms |
コンパイル使用メモリ | 113,592 KB |
実行使用メモリ | 58,272 KB |
最終ジャッジ日時 | 2024-09-22 09:48:10 |
合計ジャッジ時間 | 3,365 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 145 ms
47,828 KB |
testcase_03 | AC | 25 ms
6,940 KB |
testcase_04 | AC | 152 ms
53,184 KB |
testcase_05 | AC | 113 ms
45,972 KB |
testcase_06 | AC | 119 ms
49,284 KB |
testcase_07 | AC | 21 ms
6,940 KB |
testcase_08 | AC | 131 ms
58,272 KB |
testcase_09 | AC | 118 ms
53,496 KB |
testcase_10 | AC | 106 ms
36,844 KB |
testcase_11 | AC | 96 ms
47,948 KB |
testcase_12 | AC | 97 ms
47,676 KB |
testcase_13 | AC | 2 ms
6,948 KB |
testcase_14 | AC | 2 ms
6,940 KB |
ソースコード
#line 1 "test/yuki/No789.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/789" #include <iostream> #line 2 "src/data-structure/dynamic_segtree.hpp" #include <cassert> #include <cstddef> #include <cstdint> #include <memory> #include <vector> namespace kyopro { template <class S, auto op, auto e> class dynamic_segtree { struct Node { S val; Node *l, *r, *parent; constexpr Node(const S& v = e(), Node* pt = nullptr) : val(), l(nullptr), r(nullptr), parent(pt) {} }; using uptr = std::unique_ptr<Node>; std::vector<uptr> nodes; Node* root; Node* make_ptr(const S& v = e(), Node* pt = nullptr) { nodes.push_back(std::make_unique<Node>(v, pt)); return nodes.back().get(); }; const std::size_t n; Node* find(std::size_t i) { assert(0 <= i && i < n); std::size_t l = 0, r = n; Node* p = root; while (r - l > 1) { std::size_t md = (r + l) >> 1; if (i < md) { if (!p->l) { p->l = make_ptr(e(), p); } p = p->l; r = md; } else { if (!p->r) { p->r = make_ptr(e(), p); } p = p->r; l = md; } } return p; } void push(Node* p) { while (p = p->parent) { p->val = op((p->l ? p->l->val : e()), (p->r ? p->r->val : e())); } } public: explicit dynamic_segtree(std::size_t n = 0) : n(n), root(nullptr) { root = make_ptr(); } void apply(std::size_t i, const S& x) { assert(0 <= i && i < n); auto p = find(i); p->val = op(p->val, x); push(p); } void update(std::size_t i, const S& x) { assert(0 <= i && i < n); auto p = find(i); p->val = x; push(p); } S at(std::size_t i) { assert(0 <= i && i < n); return find(i)->val; } S fold(std::size_t l, std::size_t r) const { assert(0 <= l && l <= r && r <= n); if (l == r) { return e(); } return internal_fold(root, 0, n, l, r); } private: S internal_fold(const Node* p, std::size_t l, std::size_t r, std::size_t L, std::size_t R) const { if (!p || r <= L || R <= l) { return e(); } if (L <= l && r <= R) { return p->val; } std::size_t mid = (l + r) >> 1; return op(internal_fold(p->l, l, mid, L, R), internal_fold(p->r, mid, r, L, R)); } }; }; // namespace kyopro /** * @brief Dynamic Segment Tree * @see https://lorent-kyopro.hatenablog.com/entry/2021/03/12/025644 */ #line 2 "src/stream.hpp" #include <ctype.h> #include <stdio.h> #include <string> #line 3 "src/internal/type_traits.hpp" #include <limits> #include <numeric> #include <typeinfo> #line 7 "src/internal/type_traits.hpp" namespace kyopro { namespace internal { template <typename... Args> struct first_enabled {}; template <typename T, typename... Args> struct first_enabled<std::enable_if<true, T>, Args...> { using type = T; }; template <typename T, typename... Args> struct first_enabled<std::enable_if<false, T>, Args...> : first_enabled<Args...> {}; template <typename T, typename... Args> struct first_enabled<T, Args...> { using type = T; }; template <typename... Args> using first_enabled_t = typename first_enabled<Args...>::type; template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least { using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>, std::enable_if<dgt <= 16, std::int16_t>, std::enable_if<dgt <= 32, std::int32_t>, std::enable_if<dgt <= 64, std::int64_t>, std::enable_if<dgt <= 128, __int128_t>>; }; template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least { using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>, std::enable_if<dgt <= 16, std::uint16_t>, std::enable_if<dgt <= 32, std::uint32_t>, std::enable_if<dgt <= 64, std::uint64_t>, std::enable_if<dgt <= 128, __uint128_t>>; }; template <int dgt> using int_least_t = typename int_least<dgt>::type; template <int dgt> using uint_least_t = typename uint_least<dgt>::type; template <typename T> using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>; template <typename T> using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>; struct modint_base {}; template <typename T> using is_modint = std::is_base_of<modint_base, T>; template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>; // is_integral template <typename T> using is_integral_t = std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>>; }; // namespace internal }; // namespace kyopro /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ #line 6 "src/stream.hpp" namespace kyopro { inline void single_read(char& c) { c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); } template <typename T, internal::is_integral_t<T>* = nullptr> inline void single_read(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template <typename T, internal::is_modint_t<T>* = nullptr> inline void single_read(T& a) { long long x; single_read(x); a = T(x); } inline void single_read(std::string& str) noexcept { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } template<typename T> inline void read(T& x) noexcept {single_read(x);} template <typename Head, typename... Tail> inline void read(Head& head, Tail&... tail) noexcept { single_read(head), read(tail...); } inline void single_write(char c) noexcept { putchar_unlocked(c); } template <typename T, internal::is_integral_t<T>* = nullptr> inline void single_write(T a) noexcept { if (!a) { putchar_unlocked('0'); return; } if constexpr (std::is_signed_v<T>) { if (a < 0) putchar_unlocked('-'), a *= -1; } constexpr int d = std::numeric_limits<T>::digits10; char s[d + 1]; int now = d + 1; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now <= d) putchar_unlocked(s[now++]); } template <typename T, internal::is_modint_t<T>* = nullptr> inline void single_write(T a) noexcept { single_write(a.val()); } inline void single_write(const std::string& str) noexcept { for (auto c : str) { putchar_unlocked(c); } } template <typename T> inline void write(T x) noexcept { single_write(x); } template <typename Head, typename... Tail> inline void write(Head head, Tail... tail) noexcept { single_write(head); putchar_unlocked(' '); write(tail...); } template <typename... Args> inline void put(Args... x) noexcept { write(x...); putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief 高速入出力 */ #line 5 "test/yuki/No789.test.cpp" constexpr inline int op(int x, int y) { return x + y; } constexpr inline int e() { return 0; } using namespace std; using namespace kyopro; int main() { const size_t n = 1000000001; dynamic_segtree<int, op, e> seg(n); int q; read(q); long long ans = 0; while (q--) { int type; read(type); if (!type) { size_t x; long long y; read(x, y); seg.apply(x, y); } else { size_t l, r; read(l, r); ans += seg.fold(l, r + 1); } } put(ans); }