結果

問題 No.789 範囲の合計
コンテスト
ユーザー bolero
提出日時 2025-05-08 17:38:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,089 bytes
コンパイル時間 5,434 ms
コンパイル使用メモリ 333,364 KB
実行使用メモリ 94,752 KB
最終ジャッジ日時 2025-05-08 17:39:15
合計ジャッジ時間 17,380 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

long long op(long long a, long long b)
{
    return a + b;
}

long long e()
{
    return 0;
}

template <class S, auto op, auto e>
struct segtree
{
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

public:
    segtree() {};

    void set(int p, S x)
    {
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++)
        {
            update(p >> i);
        }
    }

    S get(int p)
    {
        return d[p + size];
    }

    S prod(int l, int r)
    {
        assert(0 <= l && l <= r);
        S sml = e(), smr = e();
        l += size, r += size;

        while (l < r)
        {
            if (l & 1)
                sml = op(sml, d[l++]);
            if (r & 1)
                smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

private:
    int size = 1 << 30, log = 30;
    std::unordered_map<long long, S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

int main()
{
    int n;
    cin >> n;

    segtree<long long, op, e> dynamic_seg;

    long long ans = 0;
    rep(_, n)
    {
        int p;
        cin >> p;
        if (p == 0)
        {
            int x, y;
            cin >> x >> y;
            dynamic_seg.set(x, dynamic_seg.get(x) + y);
        }

        if (p == 1)
        {
            int l, r;
            cin >> l >> r;
            ans += dynamic_seg.prod(l, r + 1);
        }
    }

    cout << ans << endl;

    return 0;
};
0