結果
問題 | No.1234 典型RMQ |
ユーザー | ゆにぽけ |
提出日時 | 2023-10-25 11:51:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 4,338 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 135,592 KB |
実行使用メモリ | 7,856 KB |
最終ジャッジ日時 | 2024-09-25 05:48:19 |
合計ジャッジ時間 | 7,462 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 116 ms
7,788 KB |
testcase_07 | AC | 83 ms
6,940 KB |
testcase_08 | AC | 128 ms
7,856 KB |
testcase_09 | AC | 103 ms
6,940 KB |
testcase_10 | AC | 120 ms
7,856 KB |
testcase_11 | AC | 114 ms
7,796 KB |
testcase_12 | AC | 100 ms
6,944 KB |
testcase_13 | AC | 85 ms
6,940 KB |
testcase_14 | AC | 102 ms
6,940 KB |
testcase_15 | AC | 98 ms
6,940 KB |
testcase_16 | AC | 122 ms
7,840 KB |
testcase_17 | AC | 102 ms
6,944 KB |
testcase_18 | AC | 75 ms
6,940 KB |
testcase_19 | AC | 126 ms
7,816 KB |
testcase_20 | AC | 105 ms
7,824 KB |
testcase_21 | AC | 116 ms
7,816 KB |
testcase_22 | AC | 107 ms
7,812 KB |
testcase_23 | AC | 107 ms
7,820 KB |
testcase_24 | AC | 107 ms
7,796 KB |
testcase_25 | AC | 109 ms
7,800 KB |
testcase_26 | AC | 109 ms
7,792 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,944 KB |
testcase_29 | AC | 2 ms
6,944 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cassert> #include<cmath> #include<ctime> #include<iomanip> #include<numeric> #include<stack> #include<queue> #include<map> #include<unordered_map> #include<set> #include<unordered_set> #include<bitset> #include<random> #include<functional> #include<utility> using namespace std; template<class T,T (*op)(T,T),T e(),class F,T (*mapping)(F,T),F (*composition)(F,F),F id()> struct LazySegmentTree { private: vector<T> node; vector<F> lazy; int siz,log; void map_and_comp(F f,int u) { node[u] = mapping(f,node[u]); if(u < siz) lazy[u] = composition(f,lazy[u]); } void propagate(int u) { assert(0 <= u && u < siz); map_and_comp(lazy[u],2*u); map_and_comp(lazy[u],2*u+1); lazy[u] = id(); } void recalculate(int u) {node[u] = op(node[2*u],node[2*u+1]);} public: LazySegmentTree(int n) { siz = 1; log = 0; while(siz < n) siz <<= 1,log++; node.assign(2*siz,e()); lazy.assign(siz,id()); } void fill(T x,int l = 0,int r = -1) {if(r < 0){r = siz;} for(int i = l;i < r;i++) replace(i,x);} void clear() {fill(e());} void replace(int pos,T x) {func_update(pos,x,[](T u,T v){return u = v;});} void add(int pos,T x) {func_update(pos,x,[](T u,T v){return u + v;});} void func_update(int pos,T x,T (*func)(T,T)) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); node[pos] = func(node[pos],x); for(int i = 1;i <= log;i++) recalculate(pos >> i); } T operator[](int pos) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); return node[pos]; } void apply(int pos,F f) { assert(0 <= pos && pos < siz); pos += siz; for(int i = log;i >= 1;i--) propagate(pos >> i); node[pos] = mapping(f,node[pos]); for(int i = 1;i <= log;i++) recalculate(pos >> i); } void apply(int l,int r,F f) { assert(0 <= l && l <= r && r <= siz); if(l == r) return; l += siz; r += siz; int l0 = l/(l & -l); int r0 = r/(r & -r); for(int i = log;i >= 1;i--) propagate(l0 >> i); for(int i = log;i >= 1;i--) propagate((r0-1) >> i); while(l < r) { if(l & 1) map_and_comp(f,l++); if(r & 1) map_and_comp(f,--r); l >>= 1; r >>= 1; } for(int i = 1;i <= log;i++) recalculate(l0 >> i); for(int i = 1;i <= log;i++) recalculate((r0-1) >> i); } T prod() {return node[1];} T prod(int l,int r) { assert(0 <= l && l <= r && r <= siz); l += siz; r += siz; int l0 = l/(l & -l); int r0 = r/(r & -r); for(int i = log;i >= 1;i--) propagate(l0 >> i); for(int i = log;i >= 1;i--) propagate((r0-1) >> i); T Lval = e(),Rval = e(); while(l < r) { if(l & 1) Lval = op(Lval,node[l++]); if(r & 1) Rval = op(node[--r],Rval); l >>= 1; r >>= 1; } return op(Lval,Rval); } }; int N; const int mod = 998244353; struct dat { long long Q,R; }; dat op(dat a,dat b) { if(a.Q < b.Q) return a; else if(a.Q > b.Q) return b; else { if(a.R < b.R) return a; else return b; } } dat e() {return dat{(long long)1e18,mod-1};} dat mp(int f,dat x) { x.R += f; if(x.R >= mod) x.Q++,x.R -= mod; else if(x.R < 0) x.Q--,x.R += mod; return x; } int cp(int f,int g) {return g+f;} int id() {return 0;} void solve() { cin >> N; LazySegmentTree<dat,op,e,int,mp,cp,id> seg(N); for(int i = 0;i < N;i++) { long long A; cin >> A; dat x; if(A >= 0) x.Q = A/mod,x.R = A%mod; else { x.Q = -(-A+mod-1)/mod; x.R = A-x.Q*mod; } seg.replace(i,x); } int qq; cin >> qq; while(qq--) { int k,l,r,c; cin >> k >> l >> r >> c; l--; if(k == 1) seg.apply(l,r,c); else { dat x = seg.prod(l,r); long long res = x.Q*mod+x.R; cout << res << "\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; //cin >> tt; while(tt--) solve(); }