結果

問題 No.789 範囲の合計
ユーザー AC2KAC2K
提出日時 2023-05-04 12:40:50
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,787 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 114,672 KB
実行使用メモリ 269,920 KB
最終ジャッジ日時 2024-05-01 22:37:11
合計ジャッジ時間 6,108 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 MLE -
testcase_03 AC 68 ms
8,576 KB
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 65 ms
5,376 KB
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function 'S kyopro::segtree<S, op, e>::prod(int, int) [with S = int; S (* op)(S, S) = op; S (* e)() = e]',
    inlined from 'int main()' at main.cpp:93:28:
main.cpp:52:20: warning: 'seg.kyopro::segtree<int, op, e>::n' may be used uninitialized [-Wmaybe-uninitialized]
   52 |         while (1) {
      |             ~~~~~~~^        
main.cpp: In function 'int main()':
main.cpp:77:33: note: 'seg.kyopro::segtree<int, op, e>::n' was declared here
   77 |             lg++;
      |                                 ^

ソースコード

diff # 

#line 2 "main.cpp"
#include <cassert>
#include <memory>
#line 2 "src/data-structure/hash_map.hpp"
#include <bits/stl_algobase.h>
#include <chrono>
namespace kyopro {
/// @brief HashMap
template <typename Key,
          typename Val,
          uint32_t n = 1 << 20,
          Val default_val = Val()>
class hash_map {
    using u32 = uint32_t;
    using u64 = uint64_t;

    u64* flag = new u64[n];
    Key* keys = new Key[n];
    Val* vals = new Val[n];

    static constexpr u32 shift = 64 - std::__lg(n);

    u64 r;
    u32 get_hash(const Key& k) const { return ((u64)k * r) >> shift; }

    static constexpr uint8_t mod_msk = (1 << 6) - 1;

public:
    explicit constexpr hash_map() {
        r = std::chrono::steady_clock::now().time_since_epoch().count();
        r ^= r >> 16;
        r ^= r << 32;
    }
    Val& operator[](const Key& k) {
        u32 hash = get_hash(k);

        while (1) {
            if (!(flag[hash >> 6] &
                  (static_cast<u64>(1) << (hash & mod_msk)))) {
                keys[hash] = k;
                flag[hash >> 6] |= static_cast<u64>(1) << (hash & mod_msk);
                return vals[hash] = default_val;
            }

            if (keys[hash] == k) return vals[hash];
            hash = (hash + 1) & (n - 1);
        }
    }

    Val* find(const Key& k) const {
        u32 hash = get_hash(k);
        while (1) {
            if (!(flag[hash >> 6] & (static_cast<u64>(1) << (hash & mod_msk))))
                return nullptr;
            if (keys[hash] == k) return &(vals[hash]);
            hash = (hash + 1) & (n - 1);
        }
    }
};
};  // namespace kyopro
#line 5 "main.cpp"
#include <vector>
namespace kyopro {
/// @brief Segment Tree

template <class S, S (*op)(S, S), S (*e)()>
class segtree {
    int lg, sz, n;
    hash_map<int, S, 1 << 25> dat;

public:
    segtree() {}
    segtree(int n) : segtree() {
        sz = 1, lg = 0;
        while (sz <= n) {
            sz <<= 1;
            lg++;
        }
    }
    segtree(const std::vector<S>& vec) : n((int)vec.size()) {
        sz = 1, lg = 0;
        while (sz <= n) {
            sz <<= 1;
            lg++;
        }
        for (int i = 0; i < n; i++) {
            set(i, vec[i]);
        }
        build();
    }

    void set(int p, const S& v) { dat[sz + p] = v; }
    void build() {
        for (int i = sz - 1; i > 0; i--) {
            dat[i] = op(dat[i << 1], dat[(i << 1) ^ 1]);
        }
    }
    S operator[](int p) { return dat[sz + p]; }

    void update(int p, const S& v) {
        p += sz;
        dat[p] = v;
        while (p >>= 1) {
            dat[p] = op(dat[(p << 1)], dat[(p << 1) ^ 1]);
        }
    }

    S prod(int l, int r) {
        if (l == 0 && r == n) {
            return dat[1];
        }

        l += sz, r += sz;
        S sml = e(), smr = e();
        while (l != r) {
            if (l & 1) sml = op(sml, dat[l++]);
            if (r & 1) smr = op(dat[--r], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }
    void apply(int p, const S& v) { update(p, op(dat[sz + p], v)); }
};
};  // namespace kyopro

/// @docs docs/data-structure/segtree.md

/// @docs docs/data-structure/dynamic_segtree.md
#include <iostream>
inline int op(int x, int y) { return x + y; }
inline int e() { return 0; }
int main() {
    const size_t n = 1000000001;
    kyopro::segtree<int, op, e> seg(n);

    int q;
    std::cin >> q;
    long long ans = 0;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 0) {
            size_t x;
            long long y;
            std::cin >> x >> y;
            seg.apply(x, y);
        } else {
            size_t l, r;
            std::cin >> l >> r;
            ans += seg.prod(l, r + 1);
        }
    }
    std::cout << ans << '\n';
}
0