Submission #670715

#	Time	Username	Problem	Language	Result	Execution time	Memory
670715		GusterGoose27	Two Dishes (JOI19_dishes)	C++11	5 / 100	440 ms	85400 KiB

dishes

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
 
const int MAXN = 1e6;
const ll inf = 1e18;
 
int times[MAXN][2];
int score[MAXN][2];
ll pref[MAXN][2];
ll nec_time[MAXN][2];
vector<pii> updates[MAXN];
int n, m;
 
class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	ll plz = 0; // plus
	ll mlz = -inf; // max equals. If both are active, first add, then max equals
	ll mx = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	void add_to(ll nlz) {
		plz += nlz;
		mx += nlz;
		if (mlz > -inf) mlz += nlz;
	}
	void max_eq(ll nxtmx) {
		mx = max(mx, nxtmx);
		mlz = max(mlz, nxtmx);
	}
	void prop() {
		if (l) {
			l->add_to(plz);
			r->add_to(plz);
			l->max_eq(mlz);
			r->max_eq(mlz);
		}
		plz = 0;
		mlz = -inf;
	}
	ll query(int lv, int rv) {
		if (lp > rv || rp < lv) return -inf;
		if (lp >= lv && rp <= rv) return mx;
		prop();
		return max(l->query(lv, rv), r->query(lv, rv));
	}
	void updadd(int lv, int rv, ll v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) return add_to(v);
		prop();
		l->updadd(lv, rv, v);
		r->updadd(lv, rv, v);
		mx = max(l->mx, r->mx);
	}
	void updmax(int lv, int rv, ll v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) return max_eq(v);
		prop();
		l->updmax(lv, rv, v);
		r->updmax(lv, rv, v);
		mx = max(l->mx, r->mx);
	}
};
 
stree *tree;
 
int bs1(ll v) {
	int mn = -1;
	int mx = m;
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (pref[cur][1] <= v) mn = cur;
		else mx = cur;
	}
	return mn;
}
 
int bs2(ll v) {
	int mn = -1;
	int mx = n;
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (pref[cur][0] > v) mx = cur;
		else mn = cur;
	}
	return mx;
}
 
// being at a point (x, y) means that you have completed y dishes by the time you complete dish x
 
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> times[i][0] >> nec_time[i][0] >> score[i][0];
		pref[i][0] = times[i][0] + ((i == 0) ? 0 : pref[i-1][0]);
	}
	for (int i = 0; i < m; i++) {
		cin >> times[i][1] >> nec_time[i][1] >> score[i][1];
		pref[i][1] = times[i][1] + ((i == 0) ? 0 : pref[i-1][1]);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (pref[i][0] > nec_time[i][0]) continue; // bs2 = lower bound
		updates[i].push_back(pii(1+bs1(nec_time[i][0]-pref[i][0]), score[i][0]));
	}
	for (int i = 0; i < m; i++) {
		if (pref[i][1] > nec_time[i][1]) continue;
		ans += score[i][1]; // bs1 = upper bound
		if (nec_time[i][1] >= pref[i][1]+pref[n-1][0]) continue;
		updates[bs2(nec_time[i][1]-pref[i][1])].push_back(pii(i, -score[i][1]));
	}
	tree = new stree(0,m);
	for (int i = n-1; i >= 0; i--) {
		sort(updates[i].begin(), updates[i].end(), greater<pii>());
		for (pii upd: updates[i]) {
			tree->updadd(0, upd.first, upd.second);
			tree->updmax(0, upd.first, tree->query(upd.first+1, m));
		}
	}
	cout << (ans+tree->mx) << "\n";
}

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