結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2019-08-17 00:28:36 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#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-indexedLL 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;}