Submission #1214997

#TimeUsernameProblemLanguageResultExecution timeMemory
1214997JooDdaeTwo Dishes (JOI19_dishes)C++20
100 / 100
3931 ms154648 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define mid ((l+r) >> 1) int n, m; ll a[1001001], b[1001001], s[1001001], t[1001001]; int p[1001001], q[1001001]; vector<array<ll, 2>> v[1001001]; ll tr[4004004], lz[4004004]; void lazy_update(int node, int l, int r) { if(lz[node]) { tr[node] += lz[node]; if(l != r) lz[node*2] += lz[node], lz[node*2+1] += lz[node]; lz[node] = 0; } } ll find(int nl, int nr, int node = 1, int l = 0, int r = m+1) { lazy_update(node, l, r); if(nr < l || r < nl) return -1e18; if(nl <= l && r <= nr) return tr[node]; return max(find(nl, nr, node*2, l, mid), find(nl, nr, node*2+1, mid+1, r)); } void update(int nl, int nr, ll val, int node = 1, int l = 0, int r = m+1) { lazy_update(node, l, r); if(nr < l || r < nl) return; if(nl <= l && r <= nr) { lz[node] += val; lazy_update(node, l, r); return; } update(nl, nr, val, node*2, l, mid), update(nl, nr, val, node*2+1, mid+1, r); tr[node] = max(tr[node*2], tr[node*2+1]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i] >> s[i] >> p[i]; for(int i=1;i<=m;i++) cin >> b[i] >> t[i] >> q[i]; for(int i=1;i<=n;i++) a[i] += a[i-1]; for(int i=1;i<=m;i++) b[i] += b[i-1]; for(int i=1;i<=n;i++) if(a[i] <= s[i]) { v[i].push_back({int(upper_bound(b, b+1+m, s[i]-a[i])-b-1), p[i]}); } ll sum = 0; for(int i=1;i<=m;i++) if(b[i] <= t[i]) { sum += q[i]; v[upper_bound(a, a+1+n, t[i]-b[i])-a].push_back({i-1, -q[i]}); } for(int i=0;i<=n;i++) { sort(v[i].rbegin(), v[i].rend()); for(int j=0;j<v[i].size();j++) { auto [x, y] = v[i][j]; if(j+1 < v[i].size() && v[i][j+1][0] == x) y += v[i][++j][1]; auto k = find(0, x+1)-find(x+1, x+1); if(k) update(x+1, x+1, k); update(0, x, y); } } cout << find(0, m)+sum; }
#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...