oj.uz

답안 #670715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670715 2022-12-09T23:02:35 Z GusterGoose27 Two Dishes (JOI19_dishes) C++11
5 / 100
 440 ms 85400 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 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -