結果

問題 No.789 範囲の合計
コンテスト
ユーザー kya_ski
提出日時 2020-03-28 19:54:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,270 bytes
コンパイル時間 2,249 ms
コンパイル使用メモリ 182,524 KB
実行使用メモリ 20,864 KB
最終ジャッジ日時 2025-01-02 12:05:00
合計ジャッジ時間 5,643 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 11
権限があれば一括ダウンロードができます

ソースコード

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;
    int n;
    vector<T> node;

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

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

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

    void update (int 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 (int l, int 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[] (int i) const { return node[i+n]; }

};

int main() {
    int n;
    cin >> n;
    vector<int> p;
    vector<pair<int, pair<int, int>>> data;
    for (int i = 0; i < n; i++) {
        int 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<int, int> 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);
    
    int ans = 0;
    for (const auto &e : data) {
        int op = e.first;
        if (op == 0) {
            int x;
            long long y;
            tie(x, y) = e.second;
            x = mp[x];
            seg.update(x, seg[x] + y);
        } else {
            int 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