Submission #103938

#	Time	Username	Problem	Language	Result	Execution time	Memory
103938		mzhao	Two Dishes (JOI19_dishes)	C++11	100 / 100	5561 ms	285256 KiB

dishes

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define MN 1000009
#define ll long long
#define x first
#define y second

ll N, M, A[MN], TA[MN], VA[MN], SA[MN], B[MN], TB[MN], VB[MN], SB[MN];
ll sa[MN], sb[MN], ma[MN], mb[MN];
vector<pair<ll, ll>> ver[MN], hor[MN];

ll findm(ll a[], ll len, ll x) { // index of last element <= x
	ll l = -1, h = len;
	while (l < h-1) {
		ll m = (l+h)/2;
		if (a[m] > x) h = m;
		else l = m;
	}
	return l;
}

ll t[4*MN], l[4*MN];

void push(ll n, ll a, ll b) {
	t[n] += l[n];
	if (a < b-1) {
		l[2*n] += l[n];
		l[2*n+1] += l[n];
	}
	l[n] = 0;
}

ll query(ll n, ll a, ll b, ll x, ll y) {
	if (l[n]) push(n, a, b);
	if (b <= x || y <= a) return -1e16;
	if (x <= a && b <= y) return t[n];
	return max(query(2*n, a, (a+b)/2, x, y), query(2*n+1, (a+b)/2, b, x, y));
}

ll update(ll n, ll a, ll b, ll x, ll y, ll v) {
	if (l[n]) push(n, a, b);
	if (b <= x || y <= a) return t[n];
	if (x <= a && b <= y) {
		l[n] += v;
		push(n, a, b);
	} else {
		t[n] = max(update(2*n, a, (a+b)/2, x, y, v), update(2*n+1, (a+b)/2, b, x, y, v));
	}
	return t[n];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> TA[i] >> VA[i];
		sa[i] = sa[i-1]+A[i];
	}
	for (int i = 1; i <= M; i++) {
		cin >> B[i] >> TB[i] >> VB[i];
		sb[i] = sb[i-1]+B[i];
	}
	ll cnt = 0;
	for (int i = 1; i <= N; i++) {
		ma[i] = findm(sb, M+1, TA[i]-sa[i]);
		if (VA[i] < 0) {
			cnt += VA[i];
			if (ma[i]+1 <= M) {
				hor[i-1].push_back({ma[i]+1, -VA[i]});
			}
		} else {
			ver[i].push_back({ma[i], VA[i]});
		}
	}
	for (int i = 1; i <= M; i++) {
		mb[i] = findm(sa, N+1, TB[i]-sb[i]);
		if (VB[i] < 0) {
			cnt += VB[i];
			if (mb[i]+1 > 0) {
				ver[mb[i]+1].push_back({i-1, -VB[i]});
			} else cnt -= VB[i];
		} else {
			if (mb[i] >= 0) {
				hor[mb[i]].push_back({i, VB[i]});
			}
		}
	}
	for (int i = 1; i <= N; i++) D("%lld ", ma[i]);
	D("\n");
	for (int i = 1; i <= M; i++) D("%lld ", mb[i]);
	D("\n");
	for (int i = 0; i <= N; i++) {
		for (pair<ll, ll> j : ver[i]) {
			update(1, 0, M+1, 0, j.x+1, j.y);
		}
		for (pair<ll, ll> j : hor[i]) {
			ll best = query(1, 0, M+1, 0, j.x+1);
			ll cur = query(1, 0, M+1, j.x, j.x+1);
			update(1, 0, M+1, j.x, j.x+1, best-cur);
			update(1, 0, M+1, j.x, M+1, j.y);
		}
	}
	D("cnt = %lld\n", cnt);
	cout << query(1, 0, M+1, 0, M+1)+cnt << "\n";
}

• 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