結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2019-08-16 21:35:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 597 ms / 2,000 ms |
コード長 | 2,898 bytes |
コンパイル時間 | 1,098 ms |
コンパイル使用メモリ | 104,124 KB |
実行使用メモリ | 12,396 KB |
最終ジャッジ日時 | 2024-09-22 15:16:17 |
合計ジャッジ時間 | 4,090 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<iostream>#include<string>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;const int inf=1e9+7;const ll longinf=1LL<<60 ;const ll mod=1e9+7 ;template<typename T, typename S>struct LazySegmentTree{private:int n;vector<T> node;vector<S> lazy;T E0;S E1;inline void updatef(S& lazy,S& value){lazy += value;//lazy = value;//lazy = max(lazy, value);//lazy = min(lazy, value);}inline void calculatef(T& node,S& lazy,int len){//node += lazy * len; //区間sumはこっちnode += lazy ; //区間maxとか//node = lazy ;}inline T queryf(T& x,T& y){//return x + y;//return x * y;//return max(x, y);return max(x, y);}public:LazySegmentTree(int sz,T nodeE,S lazyE ):E0(nodeE), E1(lazyE){n=1;while(n<sz)n<<=1;node.resize(2*n-1,E0);lazy.resize(2*n-1,E1);}LazySegmentTree(vector<T>& v,T E0,S E1 ):E0(E0),E1(E1){n=1;int sz=v.size();while(n<sz)n<<=1;node.resize(2*n-1,E0);lazy.resize(2*n-1,E1);rep(i,sz)node[i+n-1] = v[i];for(int i=n-2; i>=0; --i){node[i] = queryf(node[2*i+1],node[2*i+2]);}}void eval(int k,int l,int r){if(lazy[k]==E1)return ;calculatef(node[k], lazy[k], r-l);if(r-l>1){updatef(lazy[2*k+1], lazy[k]);updatef(lazy[2*k+2], lazy[k]);}lazy[k]=E1;}void update(int a, int b, S x,int k=0,int l=0,int r=-1){if(r<0)r=n;eval(k,l,r);if(r<=a||b<=l)return;if(a<=l&&r<=b){updatef(lazy[k], x);eval(k,l,r);}else {update(a,b,x,2*k+1,l,(l+r)/2);update(a,b,x,2*k+2,(l+r)/2,r);node[k]=queryf(node[2*k+1], node[2*k+2]);}}T query(int a,int b,int k=0,int l=0,int r=-1){if(r<0)r=n;eval(k,l,r);if(r<=a||b<=l)return E0;if(a<=l&&r<=b)return node[k];T xl=query(a,b,2*k+1,l,(l+r)/2);T xr=query(a,b,2*k+2,(l+r)/2,r);return queryf(xl, xr);}};int main(){int n;cin>>n;int a[n];rep(i,n)cin>>a[i];LazySegmentTree<ll,ll> sg(n+30,0,0);rep(i,n)sg.update(i, i+24, a[i]);int q;cin>>q;while(q--){int t,v;cin>>t>>v;--t;sg.update(t,t+24,v-a[t]);a[t]=v;cout<<sg.query(0,n)<<endl;}return 0;}