結果

問題 No.789 範囲の合計
ユーザー kya_skikya_ski
提出日時 2020-03-28 19:56:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 272 ms / 1,000 ms
コード長 2,411 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 188,660 KB
実行使用メモリ 25,560 KB
最終ジャッジ日時 2024-06-10 17:43:32
合計ジャッジ時間 4,797 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,520 KB
testcase_01 AC 6 ms
11,500 KB
testcase_02 AC 245 ms
24,088 KB
testcase_03 AC 95 ms
15,232 KB
testcase_04 AC 224 ms
23,792 KB
testcase_05 AC 196 ms
24,448 KB
testcase_06 AC 209 ms
24,088 KB
testcase_07 AC 85 ms
15,060 KB
testcase_08 AC 159 ms
18,920 KB
testcase_09 AC 147 ms
18,776 KB
testcase_10 AC 272 ms
25,560 KB
testcase_11 AC 209 ms
23,828 KB
testcase_12 AC 215 ms
23,820 KB
testcase_13 AC 5 ms
11,396 KB
testcase_14 AC 5 ms
11,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T> struct SegmentTree {
    using F = function<T(T, T)>;
private : 
    const T id;
    const F f;
    long long n;
    vector<T> node;

public : 
    SegmentTree (const F &f, const T id) : f(f), id(id) { }

    void init (long long sz) {
        n = 1;
        while (n < sz) n <<= 1;
        node.resize(2*n, id);
    }

    void build (vector<T> v) {
        init((long long)v.size());
        for (long long i = 0; i < (long long)v.size(); i++) node[i+n] = v[i];
        for (long long i = n-1; i > 0; i--) node[i] = f(node[i<<1|0], node[i<<1|1]);
    }

    void update (long long i, const T &x) {
        i += n;
        assert(i < node.size());
        node[i] = x;
        while (i > 0) {
            i >>= 1;
            node[i] = f(node[i<<1], node[i<<1|1]);
        }
    }

    const T query (long long l, long long r) const {
        T vl = id, vr = id;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) vl = f(vl, node[l++]);
            if (r&1) vr = f(node[--r], vr);
        }
        return f(vl, vr);
    }

    const T &operator[] (long long i) const { return node[i+n]; }

};

signed main() {
    long long n;
    cin >> n;
    vector<long long> p;
    vector<pair<long long, pair<long long, long long>>> data;
    for (long long i = 0; i < n; i++) {
        long long op, x, y;
        cin >> op >> x >> y;
        data.emplace_back(op, make_pair(x, y));
        
        if (op == 0) {
            p.emplace_back(x);
        } else {
            p.emplace_back(x);
            p.emplace_back(y);
        }
    }
    
    map<long long, long long> mp;
    sort(p.begin(), p.end());
    for (const auto &x : p) {
        mp[x] = (lower_bound(p.begin(), p.end(), x) - p.begin());
    }
    
    auto f = [](long long a, long long b) -> long long { return a + b; };
    SegmentTree<long long> seg(f, 0);
    seg.init(300300);
    
    long long ans = 0;
    for (const auto &e : data) {
        long long op = e.first;
        if (op == 0) {
            long long x;
            long long y;
            tie(x, y) = e.second;
            x = mp[x];
            seg.update(x, seg[x] + y);
        } else {
            long long l, r;
            tie(l, r) = e.second;
            l = mp[l]; r = mp[r];
            ans += seg.query(l, r+1);
        }
    }
    
    cout << ans << endl;
    return 0;
}
0