Submission #1214973

#TimeUsernameProblemLanguageResultExecution timeMemory
1214973JooDdaeTwo Dishes (JOI19_dishes)C++20
0 / 100
388 ms47688 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<int, 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, int 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=1;i<=n+1;i++) {
		sort(v[i].rbegin(), v[i].rend());
		for(auto [x, y] : v[i]) {
			auto k = find(0, x+1);
			update(x+1, x+1, k-find(x+1, x+1));
			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...