結果

問題 No.865 24時間降水量
コンテスト
ユーザー zelda_master
提出日時 2026-08-23 19:33:12
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 985 ms / 2,000 ms
+ 148µs
コード長 2,531 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 686 ms
コンパイル使用メモリ 89,024 KB
実行使用メモリ 31,744 KB
最終ジャッジ日時 2026-08-23 19:33:23
合計ジャッジ時間 5,753 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 200010;

struct Node {
    int l, r;
    LL sum, ma;
};

int n, q;
LL sum, a[N], ans[N];

struct SegTree {
    Node seg[N << 2];
    void PushUp(int u) {
        seg[u].ma = max(seg[u << 1].ma, seg[u << 1 | 1].ma);
        seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
    }
    void Build_Max(int u, int l, int r) {
        seg[u] = { l, r, 0LL, 0LL };
        if (l == r) {
            seg[u].ma = ans[l];
            return;
        }
        int mid = l + r >> 1;
        Build_Max(u << 1, l, mid), Build_Max(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void Build_Sum(int u, int l, int r) {
        seg[u] = { l, r, 0LL, 0LL };
        if (l == r) {
            seg[u].sum = a[l];
            return;
        }
        int mid = l + r >> 1;
        Build_Sum(u << 1, l, mid), Build_Sum(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void Modify(int u, int x, LL v) {
        if (seg[u].l == seg[u].r) {
            seg[u].ma = v;
            seg[u].sum = v;
            return;
        }
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= x) Modify(u << 1, x, v);
        else Modify(u << 1 | 1, x, v);
        PushUp(u);
    }
    LL Query_Max(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].ma;
        int mid = seg[u].l + seg[u].r >> 1;
        LL ret = 0LL;
        if (mid >= l) ret = max(ret, Query_Max(u << 1, l, r));
        if (mid + 1 <= r) ret = max(ret, Query_Max(u << 1 | 1, l, r));
        return ret;
    }
    LL Query_Sum(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].sum;
        int mid = seg[u].l + seg[u].r >> 1;
        LL ret = 0LL;
        if (mid >= l) ret += Query_Sum(u << 1, l, r);
        if (mid + 1 <= r) ret += Query_Sum(u << 1 | 1, l, r);
        return ret;
    }
};
SegTree sgt_sum, sgt_ma;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

    sgt_sum.Build_Sum(1, 1, n);
    for (int i = 1; i <= n - 23; ++i) {
        ans[i] = sgt_sum.Query_Sum(1, i, i + 23);
    }
    sgt_ma.Build_Max(1, 1, n - 23);
    scanf("%d", &q);
    while (q--) {
        int x, v;
        scanf("%d%d", &x, &v);
        sgt_sum.Modify(1, x, v);
        for (int i = max(1, x - 23); i <= min(n - 23, x); ++i) {
            sgt_ma.Modify(1, i, sgt_sum.Query_Sum(1, i, i + 23));
        }

        printf("%lld\n", sgt_ma.Query_Max(1, 1, n - 23));
    }

    return 0;
}
0