oj.uz

Submission #670411

# Submission time Handle Problem Language Result Execution time Memory
670411 2022-12-09T00:12:31 Z GusterGoose27 Two Dishes (JOI19_dishes) C++11
5 / 100
 409 ms 82492 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[1+bs(nec_time[i][1]-pref[i][1], 0)].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 409 ms 71412 KB Output is correct
2 Correct 401 ms 71628 KB Output is correct
3 Correct 174 ms 67572 KB Output is correct
4 Correct 333 ms 67192 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 370 ms 82492 KB Output is correct
7 Correct 103 ms 68108 KB Output is correct
8 Correct 96 ms 49596 KB Output is correct
9 Correct 189 ms 82020 KB Output is correct
10 Correct 397 ms 78092 KB Output is correct
11 Correct 135 ms 75404 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 71412 KB Output is correct
2 Correct 401 ms 71628 KB Output is correct
3 Correct 174 ms 67572 KB Output is correct
4 Correct 333 ms 67192 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 370 ms 82492 KB Output is correct
7 Correct 103 ms 68108 KB Output is correct
8 Correct 96 ms 49596 KB Output is correct
9 Correct 189 ms 82020 KB Output is correct
10 Correct 397 ms 78092 KB Output is correct
11 Correct 135 ms 75404 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23812 KB Output is correct
15 Correct 11 ms 23820 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 13 ms 23812 KB Output is correct
18 Correct 12 ms 23816 KB Output is correct
19 Incorrect 12 ms 23816 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 71412 KB Output is correct
2 Correct 401 ms 71628 KB Output is correct
3 Correct 174 ms 67572 KB Output is correct
4 Correct 333 ms 67192 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 370 ms 82492 KB Output is correct
7 Correct 103 ms 68108 KB Output is correct
8 Correct 96 ms 49596 KB Output is correct
9 Correct 189 ms 82020 KB Output is correct
10 Correct 397 ms 78092 KB Output is correct
11 Correct 135 ms 75404 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 11 ms 23764 KB Output is correct
14 Correct 11 ms 23812 KB Output is correct
15 Correct 11 ms 23820 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 13 ms 23812 KB Output is correct
18 Correct 12 ms 23816 KB Output is correct
19 Incorrect 12 ms 23816 KB Output isn't correct
20 Halted 0 ms 0 KB -