#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-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[1+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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
421 ms |
84936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
421 ms |
84936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
421 ms |
84936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
