제출 #1070174

#제출 시각아이디문제언어결과실행 시간메모리
1070174heeewTwo Dishes (JOI19_dishes)C++14
100 / 100
3739 ms230332 KiB
#include<iostream> #include<algorithm> #include<vector> using namespace std; using lint = long long; using vint = vector<int>; using pii = pair<int,int>; const int MAX_N=1000010; const lint INF=2.1e+15; struct Seg { lint sum; lint v,lazy; void setv(lint vp,lint lp) { v=max(v+lp,vp); lazy+=lp; } }; int n,m; lint t1[MAX_N],t2[MAX_N],c1[MAX_N],c2[MAX_N],s1[MAX_N],s2[MAX_N]; lint ts1[MAX_N],ts2[MAX_N],ci[MAX_N]; Seg seg[MAX_N<<2]; vint endp[MAX_N]; void update_lazy(int i) { seg[i<<1].sum+=seg[i].sum; seg[i<<1|1].sum+=seg[i].sum; seg[i<<1].setv(seg[i].v,seg[i].lazy); seg[i<<1|1].setv(seg[i].v,seg[i].lazy); seg[i].sum=0; seg[i].lazy=0; } void update_sum(int i,int s,int e,int l,int r,lint v) { if(s>=r || e<=l)return; if(l<=s && e<=r) { seg[i].sum+=v; return; } update_lazy(i); update_sum(i<<1,s,(s+e)>>1,l,r,v); update_sum(i<<1|1,(s+e)>>1,e,l,r,v); seg[i].v=min(seg[i<<1].v,seg[i<<1|1].v); } void update_(int i,int s,int e,int l,int r,lint add,lint cut) { if(s>=r || e<=l)return; if(l<=s && e<=r) { seg[i].setv(cut,add); return; } update_lazy(i); update_(i<<1,s,(s+e)>>1,l,r,add,cut); update_(i<<1|1,(s+e)>>1,e,l,r,add,cut); seg[i].v=min(seg[i<<1].v,seg[i<<1|1].v); } lint find_(int i,int s,int e,int x,int t) { if(s>x || e<=x)return 0; if(s==x && x+1==e)return seg[i].v+seg[i].sum*t; update_lazy(i); seg[i].v=min(seg[i<<1].v,seg[i<<1|1].v); return find_(i<<1,s,(s+e)>>1,x,t)+find_(i<<1|1,(s+e)>>1,e,x,t); } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> m; for(int i=1;i<=n;i++) { cin >> t1[i] >> c1[i] >> s1[i]; ts1[i]=t1[i]+ts1[i-1]; } for(int i=1;i<=m;i++) { cin >> t2[i] >> c2[i] >> s2[i]; ts2[i]=t2[i]+ts2[i-1]; } for(int i=1;i<=n;i++) { int p=upper_bound(ts2,ts2+m+1,c1[i]-ts1[i])-ts2; if(!p)continue; endp[p].push_back(i); update_sum(1,0,n+1,i,n+1,s1[i]); } for(int i=1;i<=m;i++) ci[i]=upper_bound(ts1,ts1+n+1,c2[i]-ts2[i])-ts1; for(int i=1;i<=m;i++) { vint cutted; lint cut=-INF; update_(1,0,n+1,0,ci[i],s2[i],cut); cutted.push_back(ci[i]); for(auto j : endp[i]) { update_sum(1,0,n+1,j,n+1,-s1[j]); update_(1,0,n+1,j,n+1,s1[j],cut); cutted.push_back(j); } sort(cutted.begin(),cutted.end()); for(auto p : cutted) { if(!p)continue; cut=find_(1,0,n+1,p-1,0); update_(1,0,n+1,p,n+1,0,cut); } cutted.clear(); } cout << find_(1,0,n+1,n,1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...