Submission #670715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670715	2022-12-09T23:02:35 Z	GusterGoose27	Two Dishes (JOI19_dishes)	C++11	5 / 100	440 ms	85400 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	71484 KB	Output is correct
2	Correct	440 ms	85400 KB	Output is correct
3	Correct	187 ms	81100 KB	Output is correct
4	Correct	353 ms	80936 KB	Output is correct
5	Correct	15 ms	23760 KB	Output is correct
6	Correct	405 ms	82444 KB	Output is correct
7	Correct	121 ms	68132 KB	Output is correct
8	Correct	103 ms	49480 KB	Output is correct
9	Correct	198 ms	82032 KB	Output is correct
10	Correct	415 ms	78052 KB	Output is correct
11	Correct	146 ms	75372 KB	Output is correct

Subtask #2
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23844 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23816 KB	Output is correct
6	Correct	12 ms	23836 KB	Output is correct
7	Correct	13 ms	23784 KB	Output is correct
8	Incorrect	14 ms	23892 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23844 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23816 KB	Output is correct
6	Correct	12 ms	23836 KB	Output is correct
7	Correct	13 ms	23784 KB	Output is correct
8	Incorrect	14 ms	23892 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #4
0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23844 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23816 KB	Output is correct
6	Correct	12 ms	23836 KB	Output is correct
7	Correct	13 ms	23784 KB	Output is correct
8	Incorrect	14 ms	23892 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23844 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23816 KB	Output is correct
6	Correct	12 ms	23836 KB	Output is correct
7	Correct	13 ms	23784 KB	Output is correct
8	Incorrect	14 ms	23892 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23844 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	12 ms	23816 KB	Output is correct
6	Correct	12 ms	23836 KB	Output is correct
7	Correct	13 ms	23784 KB	Output is correct
8	Incorrect	14 ms	23892 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	71484 KB	Output is correct
2	Correct	440 ms	85400 KB	Output is correct
3	Correct	187 ms	81100 KB	Output is correct
4	Correct	353 ms	80936 KB	Output is correct
5	Correct	15 ms	23760 KB	Output is correct
6	Correct	405 ms	82444 KB	Output is correct
7	Correct	121 ms	68132 KB	Output is correct
8	Correct	103 ms	49480 KB	Output is correct
9	Correct	198 ms	82032 KB	Output is correct
10	Correct	415 ms	78052 KB	Output is correct
11	Correct	146 ms	75372 KB	Output is correct
12	Correct	13 ms	23844 KB	Output is correct
13	Correct	13 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23816 KB	Output is correct
17	Correct	12 ms	23836 KB	Output is correct
18	Correct	13 ms	23784 KB	Output is correct
19	Incorrect	14 ms	23892 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	71484 KB	Output is correct
2	Correct	440 ms	85400 KB	Output is correct
3	Correct	187 ms	81100 KB	Output is correct
4	Correct	353 ms	80936 KB	Output is correct
5	Correct	15 ms	23760 KB	Output is correct
6	Correct	405 ms	82444 KB	Output is correct
7	Correct	121 ms	68132 KB	Output is correct
8	Correct	103 ms	49480 KB	Output is correct
9	Correct	198 ms	82032 KB	Output is correct
10	Correct	415 ms	78052 KB	Output is correct
11	Correct	146 ms	75372 KB	Output is correct
12	Correct	13 ms	23844 KB	Output is correct
13	Correct	13 ms	23764 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23816 KB	Output is correct
17	Correct	12 ms	23836 KB	Output is correct
18	Correct	13 ms	23784 KB	Output is correct
19	Incorrect	14 ms	23892 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Submission #670715

Compilation message