結果
問題 | No.865 24時間降水量 |
ユーザー | kzyKT |
提出日時 | 2019-08-16 21:52:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 284 ms / 2,000 ms |
コード長 | 2,110 bytes |
コンパイル時間 | 1,420 ms |
コンパイル使用メモリ | 166,140 KB |
実行使用メモリ | 13,616 KB |
最終ジャッジ日時 | 2024-09-22 15:58:13 |
合計ジャッジ時間 | 3,430 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
11,972 KB |
testcase_01 | AC | 5 ms
12,072 KB |
testcase_02 | AC | 5 ms
12,044 KB |
testcase_03 | AC | 4 ms
12,088 KB |
testcase_04 | AC | 4 ms
12,124 KB |
testcase_05 | AC | 7 ms
12,040 KB |
testcase_06 | AC | 7 ms
12,052 KB |
testcase_07 | AC | 6 ms
12,024 KB |
testcase_08 | AC | 6 ms
11,992 KB |
testcase_09 | AC | 6 ms
12,048 KB |
testcase_10 | AC | 16 ms
12,000 KB |
testcase_11 | AC | 15 ms
12,008 KB |
testcase_12 | AC | 15 ms
12,008 KB |
testcase_13 | AC | 15 ms
12,000 KB |
testcase_14 | AC | 16 ms
12,020 KB |
testcase_15 | AC | 284 ms
13,564 KB |
testcase_16 | AC | 280 ms
13,616 KB |
testcase_17 | AC | 279 ms
13,544 KB |
testcase_18 | AC | 5 ms
12,000 KB |
testcase_19 | AC | 4 ms
12,032 KB |
testcase_20 | AC | 4 ms
11,992 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;#define F first#define S second#define R cin>>#define Z class#define ll long long#define ln cout<<'\n'#define in(a) insert(a)#define pb(a) push_back(a)#define pd(a) printf("%.10f\n",a)#define mem(a) memset(a,0,sizeof(a))#define all(c) (c).begin(),(c).end()#define iter(c) __typeof((c).begin())#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)#define rep(i,n) REP(i,0,n)#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)template<Z A>void pr(A a){cout<<a;ln;}template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};typedef pair<ll,ll> P;int N=1<<18;class StarrySkyTree{public:ll Ma[555555],A[555555];void init(){memset(Ma,0,sizeof(Ma)),memset(A,0,sizeof(A));}void add(int a,int b,ll x,int k=0,int l=0,int r=N) {if(r<=a||b<=l) return;if(a<=l&&r<=b){A[k]+=x;while(k){k=(k-1)/2;Ma[k]=max(Ma[k*2+1]+A[k*2+1],Ma[k*2+2]+A[k*2+2]);}return;}add(a,b,x,k*2+1,l,(l+r)/2);add(a,b,x,k*2+2,(l+r)/2,r);}ll getMax(int a,int b,int k=0,int l=0,int r=N) {if(r<=a||b<=l)return -LLONG_MAX;if(a<=l&&r<=b)return Ma[k]+A[k];ll left=getMax(a,b,k*2+1,l,(l+r)/2),right=getMax(a,b,k*2+2,(l+r)/2,r);return max(left,right)+A[k];}};StarrySkyTree t;void Main() {t.init();ll n;cin >> n;ll a[n];rep(i,n) cin >> a[i];ll s=0;rrep(i,n) {if(i+24<n) s-=a[i+24];s+=a[i];t.add(i,i+1,s);}ll T;cin >> T;while(T--) {ll x,y;cin >> x >> y;x--;t.add(max(0LL,x-23),x+1,-a[x]);a[x]=y;t.add(max(0LL,x-23),x+1,a[x]);pr(t.getMax(0,n));}}int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}