結果
問題 | No.1234 典型RMQ |
ユーザー | kotatsugame |
提出日時 | 2020-09-18 21:38:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 432 ms / 2,000 ms |
コード長 | 2,177 bytes |
コンパイル時間 | 1,091 ms |
コンパイル使用メモリ | 86,020 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-04-26 11:03:06 |
合計ジャッジ時間 | 10,358 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 390 ms
7,936 KB |
testcase_07 | AC | 310 ms
5,376 KB |
testcase_08 | AC | 412 ms
8,064 KB |
testcase_09 | AC | 363 ms
5,760 KB |
testcase_10 | AC | 400 ms
8,064 KB |
testcase_11 | AC | 384 ms
7,936 KB |
testcase_12 | AC | 374 ms
5,632 KB |
testcase_13 | AC | 315 ms
5,376 KB |
testcase_14 | AC | 365 ms
5,632 KB |
testcase_15 | AC | 345 ms
5,632 KB |
testcase_16 | AC | 426 ms
8,064 KB |
testcase_17 | AC | 375 ms
5,632 KB |
testcase_18 | AC | 287 ms
5,376 KB |
testcase_19 | AC | 432 ms
8,064 KB |
testcase_20 | AC | 263 ms
8,320 KB |
testcase_21 | AC | 389 ms
7,936 KB |
testcase_22 | AC | 303 ms
8,192 KB |
testcase_23 | AC | 299 ms
8,192 KB |
testcase_24 | AC | 301 ms
8,192 KB |
testcase_25 | AC | 301 ms
8,192 KB |
testcase_26 | AC | 301 ms
8,192 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
コンパイルメッセージ
main.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 77 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; #include<vector> #include<functional> template<typename T> struct lazysegtree{ using F=function<T(T,T)>; using G=function<T(T,T,int,int)>; const F calcfn,lazycalcfn; const G updatefn; int n; T defvalue; vector<T>dat,lazy; vector<bool>lazyflag; lazysegtree(int n_=0,T defvalue_=0, const F calcfn_=[](T a,T b){return a+b;}, const F lazycalcfn_=[](T a,T b){return a+b;}, const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);} ):defvalue(defvalue_), calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_) { n=1; while(n<n_)n<<=1; dat.assign(2*n-1,defvalue); lazy.assign(2*n-1,T()); lazyflag.assign(2*n-1,false); } void copy(const vector<T>&v) { for(int i=0;i<v.size();i++)dat[i+n-1]=v[i]; for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]); } void eval(int i,int l,int r) { if(lazyflag[i]) { dat[i]=updatefn(dat[i],lazy[i],l,r); if(r-l>1) { lazy[2*i+1]=lazyflag[2*i+1]?lazycalcfn(lazy[2*i+1],lazy[i]):lazy[i]; lazy[2*i+2]=lazyflag[2*i+2]?lazycalcfn(lazy[2*i+2],lazy[i]):lazy[i]; lazyflag[2*i+1]=lazyflag[2*i+2]=true; } lazyflag[i]=false; } } void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; else if(a<=l&&r<=b) { lazy[k]=lazyflag[k]?lazycalcfn(lazy[k],x):x; lazyflag[k]=true; 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); dat[k]=calcfn(dat[2*k+1],dat[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return defvalue; else if(a<=l&&r<=b)return dat[k]; else return calcfn( query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r) ); } }; main() { int N; cin>>N; vector<long>A(N); for(int i=0;i<N;i++)cin>>A[i]; lazysegtree<long>P(N,(long)9e18, [](long a,long b){return a<b?a:b;}, [](long a,long b){return a+b;}, [](long a,long b,int l,int r){return a+b;}); P.copy(A); int Q; cin>>Q; for(;Q--;) { int k,l,r,c;cin>>k>>l>>r>>c; if(k==1) { P.update(l-1,r,c); } else { cout<<P.query(l-1,r)<<endl; } } }