結果
問題 | No.1234 典型RMQ |
ユーザー | monkukui2 |
提出日時 | 2020-09-18 21:40:43 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 3,065 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 106,004 KB |
実行使用メモリ | 8,188 KB |
最終ジャッジ日時 | 2023-08-08 18:35:54 |
合計ジャッジ時間 | 7,694 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 228 ms
8,036 KB |
testcase_07 | AC | 194 ms
4,380 KB |
testcase_08 | AC | 250 ms
7,836 KB |
testcase_09 | AC | 213 ms
5,436 KB |
testcase_10 | AC | 244 ms
7,892 KB |
testcase_11 | AC | 231 ms
7,500 KB |
testcase_12 | AC | 213 ms
5,680 KB |
testcase_13 | AC | 198 ms
4,380 KB |
testcase_14 | AC | 219 ms
5,416 KB |
testcase_15 | AC | 205 ms
5,328 KB |
testcase_16 | AC | 242 ms
7,936 KB |
testcase_17 | AC | 211 ms
5,328 KB |
testcase_18 | AC | 183 ms
4,380 KB |
testcase_19 | AC | 250 ms
7,708 KB |
testcase_20 | AC | 186 ms
7,756 KB |
testcase_21 | AC | 232 ms
7,708 KB |
testcase_22 | AC | 207 ms
8,188 KB |
testcase_23 | AC | 205 ms
7,836 KB |
testcase_24 | AC | 209 ms
7,760 KB |
testcase_25 | AC | 201 ms
7,708 KB |
testcase_26 | AC | 197 ms
7,792 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 1 ms
4,376 KB |
ソースコード
#include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using lint = long long; const lint INF = 100100100100100; // quoted from beet-aizu template <typename T,typename E, typename F, typename G, typename H> struct LazySegmentTree{ //using F = function<T(T,T)>; //using G = function<T(T,E)>; //using H = function<E(E,E)>; int n,height; F f; G g; H h; T ti; E ei; vector<T> dat; vector<E> laz; LazySegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n<n_) n<<=1,height++; dat.assign(2*n,ti); laz.assign(2*n,ei); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } inline T reflect(int k){ return laz[k]==ei?dat[k]:g(dat[k],laz[k]); } inline void eval(int k){ if(laz[k]==ei) return; laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]); laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]); dat[k]=reflect(k); laz[k]=ei; } inline void thrust(int k){ for(int i=height;i;i--) eval(k>>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(int a,int b,E x){ thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l<r;l>>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } }; signed main(){ lint n; cin >> n; auto f = [](lint a, lint b){ return min(a, b); }; auto g = [](lint a, lint b){ return a + b; }; auto h = [](lint a, lint b){ return a + b; }; LazySegmentTree<lint, lint, decltype(f), decltype(g), decltype(h)> sg(f, g, h, INF, 0); vector<lint> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sg.build(a); int q; cin >> q; for (int i = 0; i < q; i++) { lint k, l, r, c; cin >> k >> l >> r >> c; if (k == 1) { sg.update(l - 1, r, c); } else { cout << sg.query(l - 1, r) << endl; } } return 0; }