結果
| 問題 | No.789 範囲の合計 |
| ユーザー |
 AC2K
|
| 提出日時 | 2023-10-22 18:10:31 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 170 ms / 1,000 ms |
| コード長 | 8,358 bytes |
| コンパイル時間 | 1,378 ms |
| コンパイル使用メモリ | 112,308 KB |
| 実行使用メモリ | 58,396 KB |
| 最終ジャッジ日時 | 2023-10-22 18:10:36 |
| 合計ジャッジ時間 | 3,880 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,368 KB |
| testcase_01 | AC | 2 ms
4,368 KB |
| testcase_02 | AC | 153 ms
48,100 KB |
| testcase_03 | AC | 25 ms
4,368 KB |
| testcase_04 | AC | 170 ms
53,116 KB |
| testcase_05 | AC | 121 ms
46,252 KB |
| testcase_06 | AC | 128 ms
48,100 KB |
| testcase_07 | AC | 21 ms
4,368 KB |
| testcase_08 | AC | 143 ms
58,396 KB |
| testcase_09 | AC | 130 ms
53,116 KB |
| testcase_10 | AC | 119 ms
36,600 KB |
| testcase_11 | AC | 127 ms
47,308 KB |
| testcase_12 | AC | 100 ms
47,044 KB |
| testcase_13 | AC | 2 ms
4,368 KB |
| testcase_14 | AC | 2 ms
4,368 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);
}