#897357 (C++23) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: AC2K
• 提出日時: 2023-08-03 00:32:37
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,295 bytes
• コンパイル時間: 1,290 ms
• コンパイル使用メモリ: 94,184 KB
• 実行使用メモリ: 14,336 KB
• 最終ジャッジ日時: 2024-10-12 22:41:06
• 合計ジャッジ時間: 5,098 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
other	AC * 2 TLE * 1 -- * 12

ソースコード

#line 2 "library/src/data-structure/hash_map.hpp"
#include <bits/stl_algobase.h>
#include <chrono>
namespace kyopro {
/**
 * @brief Hash Map
 */
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 int 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

/**
 * @docs docs/data-structure/hash_map.md
 */
#line 2 "library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
namespace kyopro {
namespace internal {
/*
 * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
 */
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> struct int_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __int8_t>,
                                 std::enable_if<dgt <= 16, __int16_t>,
                                 std::enable_if<dgt <= 32, __int32_t>,
                                 std::enable_if<dgt <= 64, __int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t> >;
};
template <int dgt> struct uint_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __uint8_t>,
                                 std::enable_if<dgt <= 16, __uint16_t>,
                                 std::enable_if<dgt <= 32, __uint32_t>,
                                 std::enable_if<dgt <= 64, __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
#line 6 "library/src/stream.hpp"

namespace kyopro {
// read
void single_read(char& c) {
    c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
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>
void single_read(T& a) {
    long long x;
    single_read(x);
    a = T(x);
}
void single_read(std::string& str) {
    char c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
    while (!isspace(c)) {
        str += c;
        c = getchar_unlocked();
    }
}
template<typename T>
void read(T& x) {single_read(x);}
template <typename Head, typename... Tail>
void read(Head& head, Tail&... tail) {
    single_read(head), read(tail...);
}

// write
void single_write(char c) { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
void single_write(T a) {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if (a < 0) putchar_unlocked('-'), a *= -1;
    char s[37];
    int now = 37;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now < 37) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
void single_write(T a) {
    single_write(a.val());
}

void single_write(const std::string& str) {
    for (auto c : str) {
        putchar_unlocked(c);
    }
}

template<typename T>
void write(T x) { single_write(x); }
template <typename Head, typename... Tail> void write(Head head, Tail... tail) {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> void put(Args... x) {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief fastIO
 */
#line 3 "a.cpp"

namespace kyopro {

template <typename T, int USE = 1 << 20> class dynamic_BIT {
    hash_map<size_t, T, USE, T(0)> bit;
    int n;
    

public:
    dynamic_BIT(int n = std::numeric_limits<T>::max()) : n(n) {}

    void add(size_t p, T w) {
        p++;
        for (size_t x = p; x <= n; x += x & -x) {
            bit[x] += w;
        }
    }

    T sum(size_t p) const {
        T s = 0;

        for (size_t x = p; x > 0; x -= x & -x) {
            auto p = bit.find(x);
            if (p) s += *p;
        }
        return s;
    }

    T sum(size_t l, size_t r) const { return sum(r) - sum(l); }
};

};  // namespace kyopro

int main() {
    const size_t n = 1000001;
    kyopro::dynamic_BIT<int, n> seg;

    int q;
    kyopro::read(q);
    long long ans = 0;
    while (q--) {
        int type;
        kyopro::read(type);
        if (!type) {
            size_t x;
            long long y;
            kyopro::read(x, y);
            seg.add(x, y);
        } else {
            size_t l, r;
            kyopro::read(l, r);
            ans += seg.sum(l, r + 1);
        }
    }
    kyopro::put(ans);
}