#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using ll = long long;
const int MAXN = (int)(1e6)+5;
ll A[MAXN];
ll S[MAXN];
ll B[MAXN];
ll T[MAXN];
ll P[MAXN];
ll Q[MAXN];
ll prefA[MAXN];
ll prefB[MAXN];
ll lzy[4*MAXN];
ll mx[4*MAXN];
void push(int n) {
lzy[2*n] += lzy[n];
lzy[2*n+1] += lzy[n];
mx[2*n] += lzy[n];
mx[2*n+1] += lzy[n];
lzy[n] = 0;
}
void add(int n, int tl, int tr, int l, int r, ll ad) {
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lzy[n] += ad;
mx[n] += ad;
}
else {
push(n);
int tm = (tl + tr)/2;
add(2*n, tl, tm, l, r, ad);
add(2*n+1, tm+1, tr, l, r, ad);
mx[n] = max(mx[2*n], mx[2*n+1]);
}
}
ll query(int n, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return ll(-1e18);
}
if (l <= tl && tr <= r) {
return mx[n];
}
else {
push(n);
int tm = (tl + tr)/2;
return max(query(2*n, tl, tm, l, r), query(2*n+1, tm+1, tr, l, r));
}
}
void upd(int n, int tl, int tr, int i, ll val) {
if (tl == tr) {
mx[n] = max(mx[n], val);
lzy[n] = 0;
}
else {
push(n);
int tm = (tl + tr)/2;
if (i <= tm) {
upd(2*n, tl, tm, i, val);
}
else {
upd(2*n+1, tm+1, tr, i, val);
}
mx[n] = max(mx[2*n], mx[2*n+1]);
}
}
vector<pair<int, ll>> row[MAXN];
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, M;
cin >> N >> M;
FR(i, 4*MAXN) {
mx[i] = (ll)(-1e18);
}
for (int i = 1; i <= N; i++) {
cin >> A[i] >> S[i] >> P[i];
prefA[i] = A[i] + prefA[i-1];
}
for (int i = 1; i <= M; i++) {
cin >> B[i] >> T[i] >> Q[i];
prefB[i] = B[i] + prefB[i-1];
}
ll offset = 0;
for (int i = 1; i <= N; i++) {
if (prefA[i] <= S[i]) {
int low = 0;
int high = M;
ll g = S[i] - prefA[i];
while (low < high) {
int mid = (low + high+1)/2;
if (prefB[mid] <= g) {
low = mid;
}
else {
high = mid-1;
}
}
row[i].push_back({low, P[i]});
}
}
for (int i = 1; i <= M; i++) {
if (prefB[i] <= T[i]) {
int low = 0;
int high = N;
ll g = T[i] - prefB[i];
while (low < high) {
int mid = (low + high+1)/2;
if (prefA[mid] <= g) {
low = mid;
}
else {
high = mid-1;
}
}
if (low != N) {
offset += Q[i];
row[low+1].push_back({i-1, -Q[i]});
}
}
}
upd(1, 0, MAXN, 0, 0);
FR(i, N+1) {
sort(row[i].begin(), row[i].end());
while (row[i].size()) {
while (row[i].size() != 1) {
if (row[i][row[i].size()-1].first == row[i][row[i].size()-2].first) {
row[i][row[i].size()-2].second += row[i][row[i].size()-1].second;
row[i].pop_back();
}
else {
break;
}
}
upd(1, 0, MAXN, row[i].back().first+1, query(1, 0, MAXN, 0, row[i].back().first));
add(1, 0, MAXN, 0, row[i].back().first, row[i].back().second);
row[i].pop_back();
}
}
cout << mx[1] + offset;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
81964 KB |
Output is correct |
2 |
Incorrect |
492 ms |
82028 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
55276 KB |
Output is correct |
2 |
Correct |
34 ms |
55276 KB |
Output is correct |
3 |
Incorrect |
35 ms |
55276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
55276 KB |
Output is correct |
2 |
Correct |
34 ms |
55276 KB |
Output is correct |
3 |
Incorrect |
35 ms |
55276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
55276 KB |
Output is correct |
2 |
Correct |
34 ms |
55276 KB |
Output is correct |
3 |
Incorrect |
35 ms |
55276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
55276 KB |
Output is correct |
2 |
Correct |
34 ms |
55276 KB |
Output is correct |
3 |
Incorrect |
35 ms |
55276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
55276 KB |
Output is correct |
2 |
Correct |
34 ms |
55276 KB |
Output is correct |
3 |
Incorrect |
35 ms |
55276 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
81964 KB |
Output is correct |
2 |
Incorrect |
492 ms |
82028 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
81964 KB |
Output is correct |
2 |
Incorrect |
492 ms |
82028 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |