結果

問題 No.865 24時間降水量
ユーザー ゆきのんゆきのん
提出日時 2019-08-17 00:28:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 562 ms / 2,000 ms
コード長 1,596 bytes
コンパイル時間 1,297 ms
コンパイル使用メモリ 161,440 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-09-23 05:53:40
合計ジャッジ時間 4,285 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 4 ms
6,944 KB
testcase_02 AC 4 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 6 ms
6,944 KB
testcase_06 AC 6 ms
6,944 KB
testcase_07 AC 6 ms
6,940 KB
testcase_08 AC 6 ms
6,940 KB
testcase_09 AC 6 ms
6,940 KB
testcase_10 AC 26 ms
6,940 KB
testcase_11 AC 27 ms
6,940 KB
testcase_12 AC 27 ms
6,940 KB
testcase_13 AC 26 ms
6,940 KB
testcase_14 AC 26 ms
6,944 KB
testcase_15 AC 562 ms
7,040 KB
testcase_16 AC 561 ms
7,168 KB
testcase_17 AC 562 ms
7,040 KB
testcase_18 AC 3 ms
6,940 KB
testcase_19 AC 3 ms
6,940 KB
testcase_20 AC 3 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

const int M_N=300000;

struct BIT{
    //1-indexed
    LL bit[M_N+1],n;
    //iまでの総和を返す
    LL sum(int i){
        LL s=0;
        while(i>0){
            s+=bit[i];
            i=i&(i-1);
        }
        return s;
    }
    //iにx加算する
    void add(int i,LL x){
        while(i<=n){
            bit[i]+=x;
            i+=i&-i;
        }
    }

};



int main(){
    int n;cin >> n;
    vector<LL> a(n);
    BIT bit;
    bit.n=n+100;
    for (int i = 0;i < n; i++) {
        cin >> a[i];
        bit.add(i+2,a[i]);
    }
    LL ans = 0;
    int key = 0;
    for (int i = 0; i < n; i++) {
        if(ans < bit.sum(i+25) - bit.sum(i+1)){
            ans = bit.sum(i+25)-bit.sum(i+1);
            key = i+1;
        }
    }
    LL q;cin >> q;
    for (int i = 0; i < q; i++) {
        LL t,v;cin >> t >> v;
        if(key<=t+1&&t+1<=key+24) ans = 0;
        bit.add(t+1,-a[t-1]);
        bit.add(t+1,v);
        a[t-1]=v;
        for (int j = -24; j < 24; j++) {
            if(t+j<1) continue;
            if(ans < bit.sum(t+j+24)-bit.sum(t+j)){
                ans = bit.sum(t+j+24)-bit.sum(t+j);
                key = t+j;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
0