結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー t33f
提出日時 2019-09-12 19:16:38
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 2,029 bytes
記録
コンパイル時間 1,252 ms
コンパイル使用メモリ 83,288 KB
実行使用メモリ 11,340 KB
最終ジャッジ日時 2024-11-08 10:21:37
合計ジャッジ時間 6,071 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

class SegTree {
    using T = pair<long long, int>;
    static const T op(const T& lhs, const T& rhs) { // binary operator
        return {lhs.first + rhs.first, lhs.second + rhs.second};
    }
    constexpr static T unit = { 0, 0 }; // unit element
    const int N;
    T *data;
    static int calc_size(int sz) {
        int n = 1;
        while (sz > n) n *= 2;
        return n;
    }
public:
    explicit SegTree(int sz) : N(calc_size(sz)) {
        data = new T[2*N-1];
    }
    ~SegTree() { delete[] data; }
    T query(int a, int b, int i = -1, int l = -1, int r = -1) const {
        if (i == -1) { i = 0; l = 0; r = N; }
        // if (r <= a || b <= l) return unit; // need this if a query can be empty
        if (a <= l && r <= b) return data[i];
        int m = (l+r)/2;
        if (b <= m) return query(a, b, 2*i+1, l, m);
        if (m <= a) return query(a, b, 2*i+2, m, r);
        T v1 = query(a, b, 2*i+1, l, m),
          v2 = query(a, b, 2*i+2, m, r);
        return op(v1, v2);
    }
    void update(int i, T v) {
        int x = i + N - 1;
        data[x] = v;
        while (x > 0) {
            x = (x-1)/2;
            data[x] = op(data[2*x+1], data[2*x+2]);
        }
    }
};

struct query { int id, l, r, x; };

int main() {
    vector<query> qs;
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        qs.push_back({-1, i, 0, a});
    }
    for (int i = 0; i < q; i++) {
        int j, l, r, x; cin >> j >> l >> r >> x;
        qs.push_back({i, l, r, x});
    }
    sort(qs.begin(), qs.end(), [](query &lhs, query &rhs) {
            return lhs.x > rhs.x;
        });
    SegTree st(n);
    vector<long long> ans(q);
    for (query &q : qs) {
        if (q.id == -1) st.update(q.l, {q.x, 1});
        else {
            auto x = st.query(q.l-1, q.r);
            ans[q.id] = x.first - (long long)x.second * q.x;
        }
    }
    for (long long a : ans) cout << a << endl;
}
0