結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | mugen_1337 |
提出日時 | 2021-04-01 20:32:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,583 bytes |
コンパイル時間 | 2,469 ms |
コンパイル使用メモリ | 210,352 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-10-02 09:49:37 |
合計ジャッジ時間 | 6,573 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | AC | 208 ms
8,064 KB |
testcase_02 | AC | 208 ms
8,064 KB |
testcase_03 | AC | 194 ms
8,192 KB |
testcase_04 | AC | 198 ms
8,064 KB |
testcase_05 | AC | 195 ms
8,192 KB |
testcase_06 | AC | 72 ms
6,820 KB |
testcase_07 | AC | 37 ms
6,820 KB |
testcase_08 | AC | 147 ms
7,936 KB |
testcase_09 | AC | 169 ms
6,820 KB |
testcase_10 | AC | 120 ms
7,936 KB |
testcase_11 | AC | 105 ms
6,816 KB |
testcase_12 | AC | 132 ms
7,936 KB |
testcase_13 | AC | 122 ms
6,820 KB |
testcase_14 | AC | 47 ms
6,820 KB |
testcase_15 | AC | 105 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,816 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 998244353 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } template<typename Monoid, typename OperatorMonoid=Monoid> struct LazySegmentTree{ using F=function<Monoid(Monoid,Monoid)>; using G=function<Monoid(Monoid,OperatorMonoid)>; using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>; private: int sz,height; vector<Monoid> data; vector<OperatorMonoid> lazy; // propagate lazy value -> data (node k) inline void propagate(int k){ if(lazy[k]!=OM0){ if(k<sz){ lazy[2*k+0]=h(lazy[2*k+0],lazy[k]); lazy[2*k+1]=h(lazy[2*k+1],lazy[k]); } data[k]=g(data[k],lazy[k]); lazy[k]=OM0; } } void update(int a,int b,const OperatorMonoid &x,int k,int l,int r){ propagate(k); if(b<=l or r<=a) return ; if(a<=l and r<=b){ lazy[k]=h(lazy[k],x); propagate(k); }else{ update(a,b,x,2*k,l,(l+r)/2); update(a,b,x,2*k+1,(l+r)/2,r); data[k]=f(data[2*k],data[2*k+1]); } } Monoid query(int a,int b,int k,int l,int r){ if(b<=l or r<=a) return M1; propagate(k); if(a<=l and r<=b) return data[k]; Monoid L=query(a,b,2*k+0,l,(l+r)/2); Monoid R=query(a,b,2*k+1,(l+r)/2,r); return f(L,R); } public: const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n,const F f,const G g,const H h,const Monoid &M1,const OperatorMonoid OM0) : f(f),g(g),h(h),M1(M1),OM0(OM0) { sz=1;height=0; while(sz<n) sz<<=1,height++; data.assign(2*sz,M1);lazy.assign(2*sz,OM0); } void set(int k,const Monoid &x){ data[k+sz]=x; } void build(){ for(int k=sz-1;k>0;k--) data[k]=f(data[2*k+0],data[2*k+1]); } void update(int a,int b,const OperatorMonoid &x){ update(a,b,x,1,0,sz); } Monoid query(int a,int b){ return query(a,b,1,0,sz); } Monoid operator[](const int &k){ return query(k,k+1); } }; // range add range max using M=ll; using OM=ll; const M M1=-LINF; const OM OM0=0; M segf(M a,M b){ return (a>b?a:b); } M segg(M a,OM b){ return a+b; } OM segh(OM a,OM b){ return a+b; } signed main(){ int n;cin>>n; vector<ll> t(n-1); cin>>t; rep(i,n) t[i]-=(3ll)*i; LazySegmentTree<M,OM> seg(n,segf,segh,segg,0ll,0ll); rep(i,n) seg.set(i,t[i]); seg.build(); int q;cin>>q; while(q--){ int l,r;ll d;cin>>l>>r>>d;l--; seg.update(l,r,d); ll mx=seg.query(0,n); cout<<(3*(n-1)+mx)<<"\n"; } return 0; }