結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー kazuppa
提出日時 2025-08-09 11:19:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,499 bytes
コンパイル時間 4,416 ms
コンパイル使用メモリ 253,960 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2025-09-06 12:31:36
合計ジャッジ時間 11,444 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 3
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;

template <typename T>
struct Lazy_BIT {
    int n;
    vector<T> bit[2];
    Lazy_BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }
    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r) に加算
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }
    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    fenwick_tree<ll> b1(n + 1);
    Lazy_BIT<int> b2(n);
    for (int i = 1; i <= n; i++) b1.add(i, a[i]);

    int q;
    cin >> q;
    ll ans = 0;
    while (q--) {
        int x, l, r;
        ll y;
        cin >> x >> y >> l >> r;
        ans += b1.sum(l, r + 1);
        b2.add(l, r + 1, 1);
        ans += (y - a[x]) * (b2.sum(x) - b2.sum(x - 1));
        b1.add(x, y - a[x]);
        a[x] = y;
        cout << ans << '\n';
    }
}
0