結果
問題 | 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";}}}