#include <bits/stdc++.h>
using namespace std;
struct node {
long long mx;
long long add;
long long set;
bool both;
node() {
mx = 0;
add = 0;
set = 0;
both = false;
}
};
struct pt {
int y;
long long val;
};
const int N = 1e6 + 10;
const long long inf = 1e18;
int n, m;
long long a[N], p[N], b[N], q[N];
long long s[N], t[N];
int x[N], y[N];
vector<pt> all[N];
node st[4 * N];
void propagate(int index) {
if(2 * index + 1 < 4 * N) {
if(st[index].both) {
long long val = st[index].set + st[index].add;
st[2 * index].mx = val;
st[2 * index].set = val;
st[2 * index + 1].mx = val;
st[2 * index + 1].set = val;
st[index].add = 0;
st[index].set = 0;
st[index].both = false;
} else {
st[2 * index].mx += st[index].add;
st[2 * index].add += st[index].add;
st[2 * index + 1].mx += st[index].add;
st[2 * index + 1].add += st[index].add;
st[index].add = 0;
}
}
}
void update(int index, int l, int r, int L, int R, long long val) {
if(l > r || r < L || R < l) return;
if(L <= l && r <= R) {
st[index].mx += val;
st[index].add += val;
return;
}
propagate(index);
int mid = (l + r) / 2;
update(2 * index, l, mid, L, R, val);
update(2 * index + 1, mid + 1, r, L, R, val);
st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}
void modify(int index, int l, int r, int L, int R, long long val) {
if(l > r || r < L || R < l) return;
if(L <= l && r <= R) {
st[index].mx = val;
st[index].set = val;
st[index].both = true;
st[index].add = 0;
return;
}
propagate(index);
int mid = (l + r) / 2;
modify(2 * index, l, mid, L, R, val);
modify(2 * index + 1, mid + 1, r, L, R, val);
st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}
long long get(int index, int l, int r, int x) {
if(l > r || r < x || x < l) return -inf;
if(l == r) return st[index].mx;
propagate(index);
int mid = (l + r) / 2;
return max(get(2 * index, l, mid, x), get(2 * index + 1, mid + 1, r, x));
}
int walk(int index, int l, int r, int x, long long val) {
if(l > r || r < x) return r;
if(l == r) {
if(st[index].mx >= val) return l - 1;
return l;
}
if(st[index].mx < val) return r;
propagate(index);
int mid = (l + r) / 2;
int L = walk(2 * index, l, mid, x, val);
if(L != mid) return L;
return walk(2 * index + 1, mid + 1, r, x, val);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i];
for(int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i];
for(int i = 2; i <= n; i++) a[i] += a[i - 1];
for(int i = 2; i <= m; i++) b[i] += b[i - 1];
for(int i = 1; i <= n; i++) {
if(a[i] > s[i]) {
x[i] = -1;
continue;
}
int l = 0, r = m;
int ans = l;
while(l <= r) {
int mid = (l + r) / 2;
if(a[i] + b[mid] <= s[i]) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
x[i] = ans;
}
for(int i = 1; i <= m; i++) {
if(b[i] > t[i]) {
y[i] = -1;
continue;
}
int l = 0, r = n;
int ans = l;
while(l <= r) {
int mid = (l + r) / 2;
if(a[mid] + b[i] <= t[i]) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
y[i] = ans;
}
long long add = 0;
for(int i = 1; i <= n; i++) {
if(x[i] == -1) continue;
add += p[i];
if(x[i] < m) all[x[i] + 1].push_back({i - 1, -p[i]});
}
for(int i = 1; i <= m; i++) {
if(y[i] == -1) continue;
all[i].push_back({y[i], q[i]});
}
for(int i = 1; i <= m; i++) {
sort(all[i].begin(), all[i].end(), [&](pt p1, pt p2) {
return p1.y > p2.y;
});
}
// cout << "POINTS:\n";
// for(int i = 0; i <= m; i++) {
// for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
// }
for(int i = 0; i <= m; i++) {
// cout << "#" << i << ":\nPOINTS:\n";
for(pt p : all[i]) {
int y = p.y;
long long val = p.val;
// cout << y << " " << val << "\n";
update(1, 0, n, 0, y, val);
long long mx = get(1, 0, n, y);
int nxt = walk(1, 0, n, y + 1, mx);
if(nxt == -2) nxt = n;
// cout << mx << " " << nxt << "\n";
modify(1, 0, n, y, nxt, mx);
// cout << "TREE:\n";
// for(int j = 0; j <= n; j++) cout << get(1, 0, n, j) << " ";
// cout << "\n";
}
// cout << "\n";
}
// for(int i = 1; i <= m; i++) {
// for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
// }
// for(int i = 1; i <= n; i++) cout << x[i] << " ";
// cout << "\n";
// for(int i = 1; i <= m; i++) cout << y[i] << " ";
// cout << "\n";
// cout << add << "\n";
cout << get(1, 0, n, n) + add;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
435 ms |
180564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
150480 KB |
Output is correct |
| 2 |
Correct |
37 ms |
150416 KB |
Output is correct |
| 3 |
Correct |
34 ms |
150432 KB |
Output is correct |
| 4 |
Correct |
34 ms |
150352 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
150364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
150480 KB |
Output is correct |
| 2 |
Correct |
37 ms |
150416 KB |
Output is correct |
| 3 |
Correct |
34 ms |
150432 KB |
Output is correct |
| 4 |
Correct |
34 ms |
150352 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
150364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
150480 KB |
Output is correct |
| 2 |
Correct |
37 ms |
150416 KB |
Output is correct |
| 3 |
Correct |
34 ms |
150432 KB |
Output is correct |
| 4 |
Correct |
34 ms |
150352 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
150364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
150480 KB |
Output is correct |
| 2 |
Correct |
37 ms |
150416 KB |
Output is correct |
| 3 |
Correct |
34 ms |
150432 KB |
Output is correct |
| 4 |
Correct |
34 ms |
150352 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
150364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
150480 KB |
Output is correct |
| 2 |
Correct |
37 ms |
150416 KB |
Output is correct |
| 3 |
Correct |
34 ms |
150432 KB |
Output is correct |
| 4 |
Correct |
34 ms |
150352 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
150364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
435 ms |
180564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
435 ms |
180564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
