oj.uz

Submission #670083

# Submission time Handle Problem Language Result Execution time Memory
670083 2022-12-08T03:24:51 Z GusterGoose27 Two Dishes (JOI19_dishes) C++11
5 / 100
 420 ms 82324 KB 
#include <bits/stdc++.h>

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;
}

int 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 420 ms 81940 KB Output is correct
2 Correct 416 ms 82324 KB Output is correct
3 Correct 186 ms 77804 KB Output is correct
4 Correct 334 ms 77852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 376 ms 79568 KB Output is correct
7 Correct 97 ms 65072 KB Output is correct
8 Correct 94 ms 46448 KB Output is correct
9 Correct 178 ms 78836 KB Output is correct
10 Correct 396 ms 75156 KB Output is correct
11 Correct 142 ms 72296 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 12 ms 23764 KB Output is correct
3 Correct 12 ms 23716 KB Output is correct
4 Correct 13 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Incorrect 13 ms 23740 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 12 ms 23764 KB Output is correct
3 Correct 12 ms 23716 KB Output is correct
4 Correct 13 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Incorrect 13 ms 23740 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 12 ms 23764 KB Output is correct
3 Correct 12 ms 23716 KB Output is correct
4 Correct 13 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Incorrect 13 ms 23740 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 12 ms 23764 KB Output is correct
3 Correct 12 ms 23716 KB Output is correct
4 Correct 13 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Incorrect 13 ms 23740 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 12 ms 23764 KB Output is correct
3 Correct 12 ms 23716 KB Output is correct
4 Correct 13 ms 23800 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Incorrect 13 ms 23740 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 81940 KB Output is correct
2 Correct 416 ms 82324 KB Output is correct
3 Correct 186 ms 77804 KB Output is correct
4 Correct 334 ms 77852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 376 ms 79568 KB Output is correct
7 Correct 97 ms 65072 KB Output is correct
8 Correct 94 ms 46448 KB Output is correct
9 Correct 178 ms 78836 KB Output is correct
10 Correct 396 ms 75156 KB Output is correct
11 Correct 142 ms 72296 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23716 KB Output is correct
15 Correct 13 ms 23800 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Incorrect 13 ms 23740 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 81940 KB Output is correct
2 Correct 416 ms 82324 KB Output is correct
3 Correct 186 ms 77804 KB Output is correct
4 Correct 334 ms 77852 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 376 ms 79568 KB Output is correct
7 Correct 97 ms 65072 KB Output is correct
8 Correct 94 ms 46448 KB Output is correct
9 Correct 178 ms 78836 KB Output is correct
10 Correct 396 ms 75156 KB Output is correct
11 Correct 142 ms 72296 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23716 KB Output is correct
15 Correct 13 ms 23800 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Incorrect 13 ms 23740 KB Output isn't correct
20 Halted 0 ms 0 KB -