結果
問題 | No.2333 Slime Structure |
ユーザー |
|
提出日時 | 2023-05-28 15:06:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 324 ms / 3,000 ms |
コード長 | 1,708 bytes |
コンパイル時間 | 1,486 ms |
コンパイル使用メモリ | 85,160 KB |
実行使用メモリ | 61,600 KB |
最終ジャッジ日時 | 2024-12-27 04:42:01 |
合計ジャッジ時間 | 12,728 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #include<atcoder/segtree> using namespace std; struct dat{ long sum,L,R,M; bool e; }; dat op(dat l,dat r) { if(l.e)return r; if(r.e)return l; dat ret; ret.sum=l.sum+r.sum; ret.L=max(l.L,l.sum+r.L); ret.R=max(r.R,r.sum+l.R); ret.M=max(max(l.M,r.M),max(max(l.R,r.L),l.R+r.L)); ret.e=false; return ret; } dat e(){return(dat){0L,0L,0L,0L,true};} int N,Q; int A[1<<17]; long B[1<<17]; int Op[1<<17]; long T1[1<<17],T2[1<<17]; int main() { cin>>N; vector<long>dv; dv.push_back(0L); for(int i=0;i<N;i++) { cin>>A[i]>>B[i]; long t=dv.back()+B[i]; B[i]=t; dv.push_back(t); } cin>>Q; for(int i=0;i<Q;i++) { cin>>Op[i]>>T1[i]>>T2[i]; T1[i]--; if(Op[i]==1) { dv.push_back(T1[i]); dv.push_back(T1[i]+1); } else { dv.push_back(T1[i]); dv.push_back(T2[i]); } } sort(dv.begin(),dv.end()); dv.erase(unique(dv.begin(),dv.end()),dv.end()); vector<dat>init(dv.size()-1); int idx=0; for(int i=0;i+1<dv.size();i++) { //dv[i+1]<=B[idx] while(B[idx]<dv[i+1])idx++; //cout<<dv[i]<<"->"<<dv[i+1]<<" : "<<A[idx]<<" "<<B[idx]<<endl; init[i].sum=A[idx]*(dv[i+1]-dv[i]); init[i].L=init[i].R=init[i].M=A[idx]>=0?init[i].sum:A[idx]; init[i].e=false; } atcoder::segtree<dat,op,e>seg(init); for(int i=0;i<Q;i++) { if(Op[i]==1) { int j=lower_bound(dv.begin(),dv.end(),T1[i])-dv.begin(); assert(dv[j+1]==T1[i]+1); seg.set(j,(dat){T2[i],T2[i],T2[i],T2[i],false}); } else { int l=lower_bound(dv.begin(),dv.end(),T1[i])-dv.begin(); int r=lower_bound(dv.begin(),dv.end(),T2[i])-dv.begin(); assert(dv[l]==T1[i]&&dv[r]==T2[i]); cout<<seg.prod(l,r).M<<"\n"; } } }