Submission #1214995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214995		JooDdae	Two Dishes (JOI19_dishes)	C++20	100 / 100	3751 ms	154484 KiB

dishes

#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=1;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;
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9