oj.uz

Submission #670084

# Submission time Handle Problem Language Result Execution time Memory
670084 2022-12-08T03:25:26 Z GusterGoose27 Two Dishes (JOI19_dishes) C++11
5 / 100
 423 ms 72180 KB 
#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 bs(ll v, bool b) {
	int mn = -1;
	int mx = ((b == 0) ? n : m);
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (pref[cur][b] <= v) mn = cur;
		else mx = cur;
	}
	return mn;
}

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+bs(nec_time[i][0]-pref[i][0], 1), 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[bs(nec_time[i][1]-pref[i][1], 0)+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 423 ms 71904 KB Output is correct
2 Correct 405 ms 72180 KB Output is correct
3 Correct 182 ms 68136 KB Output is correct
4 Correct 343 ms 67800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 366 ms 69772 KB Output is correct
7 Correct 101 ms 61940 KB Output is correct
8 Correct 94 ms 43116 KB Output is correct
9 Correct 180 ms 68028 KB Output is correct
10 Correct 418 ms 71216 KB Output is correct
11 Correct 135 ms 68024 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 71904 KB Output is correct
2 Correct 405 ms 72180 KB Output is correct
3 Correct 182 ms 68136 KB Output is correct
4 Correct 343 ms 67800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 366 ms 69772 KB Output is correct
7 Correct 101 ms 61940 KB Output is correct
8 Correct 94 ms 43116 KB Output is correct
9 Correct 180 ms 68028 KB Output is correct
10 Correct 418 ms 71216 KB Output is correct
11 Correct 135 ms 68024 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 13 ms 23752 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23816 KB Output is correct
16 Correct 12 ms 23756 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Incorrect 13 ms 23764 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 71904 KB Output is correct
2 Correct 405 ms 72180 KB Output is correct
3 Correct 182 ms 68136 KB Output is correct
4 Correct 343 ms 67800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 366 ms 69772 KB Output is correct
7 Correct 101 ms 61940 KB Output is correct
8 Correct 94 ms 43116 KB Output is correct
9 Correct 180 ms 68028 KB Output is correct
10 Correct 418 ms 71216 KB Output is correct
11 Correct 135 ms 68024 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 13 ms 23752 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23816 KB Output is correct
16 Correct 12 ms 23756 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Incorrect 13 ms 23764 KB Output isn't correct
20 Halted 0 ms 0 KB -