結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー otogawa
提出日時 2025-04-22 08:33:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 1,274 bytes
コンパイル時間 1,951 ms
コンパイル使用メモリ 198,476 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2025-04-22 08:33:39
合計ジャッジ時間 5,953 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

struct Bit {
    int n;
    vector<int> bit;
    Bit(int _n) : n(_n), bit(n + 1) {}

    void add(int i, int x) {
        for (i++ ; i <= n; i += i & -i) {
            bit[i] += x;
        }
    }
    void add(int l, int r, int x) {
        add(l, x);
        add(r + 1, -x);
    }
    int sum(int i) {
        int ret = 0;
        for (i++; i; i -= i & -i) {
            ret += bit[i];
        }
        return ret;
    }
};

int32_t main() {
    fast_io;

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (auto &i : a) cin >> i;

    vector<tuple<int, int, int>> queries(q);
    for (auto &[t, l, r] : queries) {
        char x; cin >> x;
        t = x == 'B';
        cin >> l >> r;
    }

    reverse(queries.begin(), queries.end());
    vector<int> b(n);

    Bit bit(n);
    for (auto [t, l, r] : queries) {
        if (t) {
            --l, --r;
            bit.add(l, r, 1);
        } else {
            int i = l - 1, x = r;

            b[i] += x * bit.sum(i);
        }
    }
    for (int i = 0; i < n; i++) {
        b[i] += a[i] * bit.sum(i);
        cout << b[i] << " \n"[i == n - 1];
    }

}
0