結果
問題 | No.789 範囲の合計 |
ユーザー | Ryoich |
提出日時 | 2022-12-28 02:29:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 96 ms / 1,000 ms |
コード長 | 4,727 bytes |
コンパイル時間 | 2,703 ms |
コンパイル使用メモリ | 208,304 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-05-02 04:45:44 |
合計ジャッジ時間 | 4,576 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 90 ms
6,016 KB |
testcase_03 | AC | 62 ms
5,376 KB |
testcase_04 | AC | 96 ms
6,144 KB |
testcase_05 | AC | 73 ms
5,760 KB |
testcase_06 | AC | 78 ms
6,016 KB |
testcase_07 | AC | 47 ms
5,376 KB |
testcase_08 | AC | 76 ms
6,656 KB |
testcase_09 | AC | 69 ms
6,144 KB |
testcase_10 | AC | 82 ms
5,376 KB |
testcase_11 | AC | 55 ms
6,144 KB |
testcase_12 | AC | 55 ms
6,272 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; // clang-format off #define rep(i, n) for (ll i = 0; i < ll(n); i++) #define drep(i, n) for (ll i = ll(n - 1); i >= 0; i--) #define rng(a) (a).begin(), (a).end() #define rrng(a) (a).rbegin(), (a).rend() #define sz(x) (ll)(x).size() #define cto const auto& #define popcount __builtin_popcount #ifdef _DEBUG #include <debug_print.hpp> #define deb(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define deb(...) (static_cast<void>(0)) #endif template<class T> inline bool chmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; } template<class T> inline bool chmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; } template<class T> inline void print_vec(const vector<T>& x) { rep(i, sz(x)) cout << x[i] << " \n"[i+1==sz(x)]; } template<class T> inline void uniq_vec(vector<T>& x) { sort(rng(x)); x.erase(unique(rng(x)), x.end()); } inline void FASTER_IO() { cin.tie(0)->sync_with_stdio(false); cout << fixed << setprecision(20); } // clang-format on using ld = long double; using P = pair<int, int>; constexpr char el = '\n'; constexpr int INF = 1001001001; constexpr ll LINF = 2e18; constexpr int mod = 1000000007; // 1. A set S equipped with a binary operation S × S → S // 2. Associativity // 3. Identity element template <class Monoid> class DynamicSegmentTree { using F = function<Monoid(Monoid, Monoid)>; struct Node; using Node_ptr = unique_ptr<Node>; struct Node { size_t idx; Monoid val, product; Node_ptr left, right; Node(size_t idx, Monoid val) : idx(idx), val(val), product(val), left(nullptr), right(nullptr) {} void update(const DynamicSegmentTree& x) { const auto& combine = x.combine; const auto& id = x.identity; product = combine(left ? left->product : id, right ? right->product : id); product = combine(product, val); } }; const size_t n; Node_ptr root; F combine; Monoid identity; void set(Node_ptr& t, size_t l, size_t r, size_t i, Monoid val) const { if (!t) { t = make_unique<Node>(i, val); return; } if (t->idx == i) { t->val = val; t->update(*this); return; } size_t mid = (l + r) >> 1; if (i < mid) { if (t->idx < i) swap(t->idx, i), swap(t->val, val); set(t->left, l, mid, i, val); } else { if (t->idx > i) swap(t->idx, i), swap(t->val, val); set(t->right, mid, r, i, val); } t->update(*this); } Monoid get(const Node_ptr& t, size_t l, size_t r, size_t i) const { if (!t) return identity; if (t->idx == i) return t->val; size_t mid = (l + r) >> 1; return i < mid ? get(t->left, l, mid, i) : get(t->right, mid, r, i); } Monoid fold(const Node_ptr& t, size_t a, size_t b, size_t l, size_t r) const { if (!t || b <= l || r <= a) return identity; if (l <= a && b <= r) return t->product; size_t c = (a + b) >> 1; Monoid res = fold(t->left, a, c, l, r); if (l <= t->idx && t->idx < r) res = combine(res, t->val); return combine(res, fold(t->right, c, b, l, r)); } void reset(Node_ptr& t, size_t a, size_t b, size_t l, size_t r) const { if (!t || b <= l || r <= a) return; if (l <= a && b <= r) { t.reset(); return; } size_t c = (a + b) >> 1; reset(t->left, a, c, l, r); reset(t->right, c, b, l, r); t->update(*this); } public: DynamicSegmentTree(size_t n, const F& combine, Monoid identity) : n(n), combine(combine), identity(identity), root(nullptr) {} // set a[i] = val void set(size_t i, Monoid val) { set(root, 0, n, i, val); } // return value in a[i] Monoid get(size_t i) const { return get(root, 0, n, i); } // return combine[l, r) Monoid fold(size_t l, size_t r) const { return fold(root, 0, n, l, r); } Monoid all_fold() const { return root ? root->product : identity; } void reet(size_t l, size_t r) { reset(root, 0, n, l, r); } }; int main() { FASTER_IO(); DynamicSegmentTree<ll> seg( 1e10, [](ll x, ll y) { return x + y; }, 0ll); int q; cin >> q; ll ans = 0; while (q--) { int type; cin >> type; if (type == 0) { int i; ll val; cin >> i >> val; seg.set(i, seg.get(i) + val); } else { int l, r; cin >> l >> r; ans += seg.fold(l, r + 1); } } cout << ans << el; return 0; }