oj.uz

답안 #670410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670410 2022-12-09T00:09:24 Z GusterGoose27 Two Dishes (JOI19_dishes) C++11
0 / 100
 413 ms 81088 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 = 0;
	int mx = n-1;
	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]+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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 71392 KB Output is correct
2 Correct 410 ms 71680 KB Output is correct
3 Correct 184 ms 81088 KB Output is correct
4 Incorrect 350 ms 81036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 71392 KB Output is correct
2 Correct 410 ms 71680 KB Output is correct
3 Correct 184 ms 81088 KB Output is correct
4 Incorrect 350 ms 81036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 71392 KB Output is correct
2 Correct 410 ms 71680 KB Output is correct
3 Correct 184 ms 81088 KB Output is correct
4 Incorrect 350 ms 81036 KB Output isn't correct
5 Halted 0 ms 0 KB -