結果

問題 No.789 範囲の合計
ユーザー kya_skikya_ski
提出日時 2020-03-28 19:56:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 276 ms / 1,000 ms
コード長 2,411 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 185,308 KB
実行使用メモリ 25,404 KB
最終ジャッジ日時 2023-08-30 18:08:12
合計ジャッジ時間 5,524 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,536 KB
testcase_01 AC 5 ms
11,376 KB
testcase_02 AC 247 ms
23,960 KB
testcase_03 AC 91 ms
15,244 KB
testcase_04 AC 232 ms
23,528 KB
testcase_05 AC 209 ms
24,120 KB
testcase_06 AC 212 ms
24,096 KB
testcase_07 AC 80 ms
15,080 KB
testcase_08 AC 158 ms
18,876 KB
testcase_09 AC 148 ms
18,320 KB
testcase_10 AC 276 ms
25,404 KB
testcase_11 AC 213 ms
23,520 KB
testcase_12 AC 216 ms
23,700 KB
testcase_13 AC 5 ms
11,296 KB
testcase_14 AC 4 ms
11,320 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