結果

問題 No.789 範囲の合計
ユーザー はまやんはまやんはまやんはまやん
提出日時 2019-02-09 09:14:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 162 ms / 1,000 ms
コード長 3,999 bytes
コンパイル時間 1,671 ms
コンパイル使用メモリ 174,636 KB
実行使用メモリ 19,520 KB
最終ジャッジ日時 2024-07-01 11:54:07
合計ジャッジ時間 3,798 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 147 ms
16,384 KB
testcase_03 AC 47 ms
6,940 KB
testcase_04 AC 162 ms
17,988 KB
testcase_05 AC 127 ms
15,872 KB
testcase_06 AC 133 ms
16,384 KB
testcase_07 AC 37 ms
6,944 KB
testcase_08 AC 143 ms
19,520 KB
testcase_09 AC 130 ms
17,984 KB
testcase_10 AC 122 ms
11,904 KB
testcase_11 AC 98 ms
16,256 KB
testcase_12 AC 104 ms
16,256 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct DynamicSegTree {
    // ----------------------- modidy!! -------------------------------
    using T = ll;
    static const T def = 0;
    inline T comp(T a, T b) { return a + b; }
    // ----------------------------------------------------------------

    struct Node { int lft, rht; T val; Node(int _lft, int _rht, T _val) : lft(_lft), rht(_rht), val(_val) {} };
    deque<Node> deq;
    int root, width, sz;

    DynamicSegTree() {
        deq.push_back(Node(-1, -1, def));
        root = 0;
        width = 1;
        sz = 1;
    }

    int create(int parent, bool is_right) {
        int i = deq.size();
        deq.push_back(Node(-1, -1, def));
        if (is_right) deq[parent].rht = i;
        else deq[parent].lft = i;
        return i;
    }
    void update(int i, T v) {
        assert(0 <= i);
        while (width <= i) {
            Node node(root, -1, deq[root].val);
            root = deq.size();
            deq.push_back(node);
            width *= 2;
        }
        update(root, -1, false, 0, width, i, v);
    }
    void update(int i, int parent, bool is_right, int il, int ir, int j, T v) {
        if (il == j and ir == j + 1) {
            if (i == -1) { i = create(parent, is_right); sz += 1; }
            deq[i].val = v;
        }
        else if (ir <= j or j + 1 <= il) {
        }
        else {
            if (i == -1) i = create(parent, is_right);
            update(deq[i].lft, i, false, il, (il + ir) / 2, j, v);
            update(deq[i].rht, i, true, (il + ir) / 2, ir, j, v);

            T lft = def;
            if (0 <= deq[i].lft) lft = deq[deq[i].lft].val;
            T rht = def;
            if (0 <= deq[i].rht) rht = deq[deq[i].rht].val;

            deq[i].val = comp(lft, rht);
        }
    }
    T get(int l, int r) {
        assert(0 <= l and l <= r);
        if (width <= l) return def;
        return get(root, 0, width, l, min(width, r));
    }
    T get(int i, int il, int ir, int l, int r) {
        if (i == -1) return def;
        if (l <= il and ir <= r) {
            return deq[i].val;
        }
        else if (ir <= l or r <= il) {
            return def;
        }
        else {
            return comp(get(deq[i].lft, il, (il + ir) / 2, l, r), get(deq[i].rht, (il + ir) / 2, ir, l, r));
        }
    }
    T get(int i) { return get(i, i + 1); }

    void add(int i, T v) { update(i, get(i) + v); }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/








int N;
DynamicSegTree dst;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    ll ans = 0;
    rep(i, 0, N) {
        int t, x, y; cin >> t >> x >> y;
        if (t == 0) {
            dst.add(x, y);
        }
        else {
            ans += dst.get(x, y+1);
        }
    }

    cout << ans << endl;
}
0