제출 #1091732

#제출 시각아이디문제언어결과실행 시간메모리
109173212345678Two Dishes (JOI19_dishes)C++17
0 / 100
283 ms36264 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int nx=1e6+5; ll n, m, qsa[nx], qsb[nx], st[nx], tt[nx], p[nx], q[nx], res, tmp; vector<tuple<ll, ll, ll>> v; struct segtree { ll d[4*nx], lz[4*nx]; void pushlz(int l, int r, int i) { d[i]+=lz[i]; if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i]; lz[i]=0; } void update(int l, int r, int i, int idx, ll vl) { pushlz(l, r, i); if (r<idx||idx<l) return; if (l==r) return d[i]=max(d[i], vl), void(); int md=(l+r)/2; update(l, md, 2*i, idx, vl); update(md+1, r, 2*i+1, idx, vl); d[i]=max(d[2*i], d[2*i+1]); } void updaterange(int l, int r, int i, int ql, int qr, ll vl) { pushlz(l, r, i); if (qr<l||r<ql) return; if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void(); int md=(l+r)/2; updaterange(l, md ,2*i, ql, qr, vl); updaterange(md+1, r, 2*i+1, ql, qr, vl); d[i]=max(d[2*i], d[2*i+1]); } ll query(int l, int r, int i ,int ql, int qr) { pushlz(l, r, i); if (qr<l||r<ql) return -1e18; if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr)); } } s; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=n ;i++) cin>>qsa[i]>>st[i]>>p[i], qsa[i]+=qsa[i-1]; for (int i=1; i<=m; i++) cin>>qsb[i]>>tt[i]>>q[i], qsb[i]+=qsb[i-1]; for (int i=1; i<=n; i++) { if (st[i]<qsa[i]) continue; ll x=upper_bound(qsb, qsb+m+1, st[i]-qsa[i])-qsb-1; if (x!=m) v.push_back({i-1, -(x+1), -p[i]}); res+=p[i]; } for (int i=1; i<=m; i++) { if (tt[i]<qsb[i]) continue; ll x=upper_bound(qsa, qsa+n+1, tt[i]-qsb[i])-qsa-1; if (x==n) res+=q[i]; else v.push_back({x, -i, q[i]}); } sort(v.begin(), v.end()); s.updaterange(0, m, 1, 1, m, -1e18); for (auto [x, y, vl]:v) { y=-y; tmp=s.query(0, m, 1, 0, y); s.update(0, m, 1, y, tmp+vl); if (y!=m) s.updaterange(0, m, 1, y+1, m, vl); } cout<<res+s.query(0, m, 1, 0, m); }
#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...