結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー | beet |
提出日時 | 2019-08-06 19:50:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,089 bytes |
コンパイル時間 | 2,387 ms |
コンパイル使用メモリ | 216,720 KB |
実行使用メモリ | 17,472 KB |
最終ジャッジ日時 | 2023-09-06 16:04:12 |
合計ジャッジ時間 | 16,360 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 3 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 337 ms
15,920 KB |
testcase_12 | AC | 330 ms
16,060 KB |
testcase_13 | AC | 233 ms
16,128 KB |
testcase_14 | AC | 327 ms
16,828 KB |
testcase_15 | AC | 368 ms
16,768 KB |
testcase_16 | AC | 378 ms
16,432 KB |
testcase_17 | AC | 438 ms
16,836 KB |
testcase_18 | AC | 431 ms
16,732 KB |
testcase_19 | AC | 100 ms
16,464 KB |
testcase_20 | AC | 103 ms
16,956 KB |
testcase_21 | AC | 103 ms
16,576 KB |
testcase_22 | AC | 103 ms
17,444 KB |
testcase_23 | AC | 105 ms
17,368 KB |
testcase_24 | AC | 84 ms
17,236 KB |
testcase_25 | AC | 87 ms
16,792 KB |
testcase_26 | AC | 85 ms
16,728 KB |
testcase_27 | AC | 86 ms
16,708 KB |
testcase_28 | AC | 88 ms
16,608 KB |
testcase_29 | AC | 344 ms
16,520 KB |
testcase_30 | AC | 373 ms
17,472 KB |
testcase_31 | AC | 400 ms
16,992 KB |
testcase_32 | AC | 99 ms
16,632 KB |
testcase_33 | TLE | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template <typename T,typename E> struct SegmentTree{ 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; SegmentTree(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); } template<typename Uku, typename Check, typename Func, typename U> void update(int a,int b,Uku uku,Check check,Func func,U x,int l,int r,int k){ if(l+1<r) eval(k); if(r<=a||b<=l||uku(reflect(k))) return; if(a<=l&&r<=b&&check(reflect(k))){ tie(dat[k],laz[k])=func(reflect(k),x); if(l+1<r) eval(k); return; } int m=(l+r)>>1; update(a,b,uku,check,func,x,l,m,(k<<1)|0); update(a,b,uku,check,func,x,m,r,(k<<1)|1); dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } template<typename Uku, typename Check, typename Func, typename U> void update(int a,int b,Uku uku,Check check,Func func,U x){ update(a,b,uku,check,func,x,0,n,1); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; using ll = long long; struct T{ ll ma,mi,len,sum; T(ll ma,ll mi,ll len,ll sum):ma(ma),mi(mi),len(len),sum(sum){} }; using E = ll; auto f=[&](T a,T b){ return T(max(a.ma,b.ma),min(a.mi,b.mi),a.len+b.len,a.sum+b.sum); }; auto g=[&](T a,E b){ return T(b,b,a.len,a.len*b); }; auto h=[&](E a,E b){ (void)a; assert(~b); return b; }; const ll INF = 1e9+1; T ti(-INF,+INF,0,0); E ei(-1); SegmentTree<T, E> seg(f,g,h,ti,ei); vector<T> vt; for(int i=0;i<n;i++) vt.emplace_back(as[i],as[i],1,as[i]); seg.build(vt); for(int i=0;i<q;i++){ int t; cin>>t; if(t==1){ int l,r,x; cin>>l>>r>>x; l--; seg.update(l,r,x); } if(t==2){ using U = ll; auto uku=[&](T a){return a.ma==1;}; auto check=[&](T a){return a.ma==a.mi;}; auto func=[&](T a,U x){ assert(check(a)); return make_pair(a,E(__gcd(a.ma,x))); }; int l,r; cin>>l>>r; l--; U x; cin>>x; seg.update(l,r,uku,check,func,x); } if(t==3){ int l,r; cin>>l>>r; l--; cout<<seg.query(l,r).ma<<"\n"; } if(t==4){ int l,r; cin>>l>>r; l--; cout<<seg.query(l,r).sum<<"\n"; } } cout<<flush; return 0; }