#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2000010;
int N, M;
ll A[maxn], B[maxn], S[maxn], T[maxn], P[maxn], Q[maxn], nA[maxn], nB[maxn], nS[maxn], nT[maxn], nP[maxn], nQ[maxn];
int X[maxn], Y[maxn], inv[maxn], pnt[maxn];
pii ord[maxn];
vector<int> adj1[maxn], adj2[maxn];
ll dp[maxn];
ll offset;
struct BIT {
ll tree[4 * maxn];
ll lazy[4 * maxn];
void init() {
for(int i = 0; i < 4 * N; i++) {
tree[i] = -1e17;
lazy[i] = 0;
}
}
void prop(int l, int r, int n) {
if(l != r) {
tree[n << 1] += lazy[n];
lazy[n << 1] += lazy[n];
tree[n << 1 + 1] += lazy[n];
lazy[n << 1 + 1] += lazy[n];
lazy[n] = 0;
}
}
void upd(int a, int b, ll d, int l, int r, int n) {
if(b < l || r < a) return;
if(a <= l && r <= b) {
tree[n] += d;
lazy[n] += d;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd(a, b, d, l, m, n << 1);
upd(a, b, d, m + 1, r, n << 1 + 1);
tree[n] = max(tree[n << 1], tree[n << 1 + 1]);
}
void upd2(int x, ll v, int l, int r, int n) {
if(x < l || r < x) return;
if(l == r) {
tree[n] = v;
return;
}
prop(l, r, n);
int m = (l + r)>>1;
upd2(x, v, l, m, n << 1);
upd2(x, v, m + 1, r, n << 1 + 1);
tree[n] = max(tree[n << 1], tree[n << 1 + 1]);
}
ll quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return -1e18;
if(a <= l && r <= b) return tree[n];
prop(l, r, n);
int m = (l + r)>>1;
ll L = quer(a, b, l, m, n << 1);
ll R = quer(a, b, m + 1, r, n << 1 + 1);
return max(L, R);
}
} bit;
void proc() {
for(int i = 0; i < N; i++) {
if(A[i] > S[i]) P[i] = 0;
int s = 0, e = M - 1, p = M;
while(s <= e) {
int m = (s + e)>>1;
if(A[i] + B[m] > S[i]) {
p = m;
e = m - 1;
}
else s = m + 1;
}
X[i] = p;
}
for(int i = 0; i < M; i++) {
if(B[i] > T[i]) Q[i] = 0;
int s = 0, e = N - 1, p = N;
while(s <= e) {
int m = (s + e)>>1;
if(B[i] + A[m] > T[i]) {
p = m;
e = m - 1;
}
else s = m + 1;
}
Y[i] = p;
}
for(int i = 0; i < M; i++) adj1[i].clear();
for(int i = 0; i < N; i++) adj2[i].clear();
for(int i = 0; i < N; i++) adj1[ X[i] ].push_back(i);
for(int i = 0; i < M; i++) adj2[ Y[i] ].push_back(i);
}
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
}
for(int i = 0; i < M; i++) {
scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
}
for(int i = 1; i < N; i++) A[i] += A[i - 1];
for(int i = 1; i < M; i++) B[i] += B[i - 1];
proc();
for(int i = 0; i < N; i++) if(P[i] < 0) offset += P[i];
for(int i = 0; i < M; i++) if(Q[i] < 0) offset += Q[i];
int cnt1 = 0;
int cnt2 = 0;
for(int i = 0; i < N; i++) {
if(P[i] >= 0) {
nA[cnt1] = A[i];
nS[cnt1] = S[i];
nP[cnt1] = P[i];
cnt1++;
}
else {
nA[cnt1] = A[i];
nS[cnt1] = S[i];
nP[cnt1] = 0;
cnt1++;
}
for(int j = 0; j < adj2[i].size(); j++) {
int k = adj2[i][j];
if(Q[k] < 0) {
nA[cnt1] = A[i];
nS[cnt1] = A[i] + B[k] - 1;
nP[cnt1] = -Q[k];
cnt1++;
}
}
}
for(int i = 0; i < M; i++) {
if(Q[i] >= 0) {
nB[cnt2] = B[i];
nT[cnt2] = T[i];
nQ[cnt2] = Q[i];
cnt2++;
}
else {
nB[cnt2] = B[i];
nT[cnt2] = T[i];
nQ[cnt2] = 0;
cnt2++;
}
for(int j = 0; j < adj1[i].size(); j++) {
int k = adj1[i][j];
if(P[k] < 0) {
nB[cnt2] = B[i];
nT[cnt2] = B[i] + A[k] - 1;
nQ[cnt2] = -P[k];
cnt2++;
}
}
}
N = cnt1;
M = cnt2;
for(int i = 0; i < N; i++) {
A[i] = nA[i];
S[i] = nS[i];
P[i] = nP[i];
}
for(int i = 0; i < M; i++) {
B[i] = nB[i];
T[i] = nT[i];
Q[i] = nQ[i];
}
proc();
//*/
for(int i = 0; i < N; i++) ord[i] = pii(X[i], -i);
sort(ord, ord + N);
for(int i = 0; i < N; i++) inv[ -ord[i].second ] = i;
int pos = 0;
for(int i = 0; i < M; i++) {
while(pos < N && ord[pos].first <= i) pos++;
pnt[i] = pos - 1;
}
for(int i = 0; i < M; i++) offset += Q[i];
bit.init();
for(int i = N - 1; i >= 0; i--) {
dp[i] = bit.quer(inv[i] + 1, N - 1, 0, N - 1, 1);
dp[i] = max(0LL, dp[i]);
bit.upd2(inv[i], dp[i], 0, N - 1, 1);
bit.upd(0, inv[i], P[i], 0, N - 1, 1);
for(int j = 0; j < adj2[i].size(); j++) {
int k = adj2[i][j];
bit.upd(0, pnt[k], -Q[k], 0, N - 1, 1);
}
}
ll ans = bit.quer(0, N - 1, 0, N - 1, 1);
ans = max(0LL, ans);
printf("%lld", ans + offset);
}
Compilation message
dishes.cpp: In member function 'void BIT::prop(int, int, int)':
dishes.cpp:31:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
tree[n << 1 + 1] += lazy[n];
~~^~~
dishes.cpp:32:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
lazy[n << 1 + 1] += lazy[n];
~~^~~
dishes.cpp: In member function 'void BIT::upd(int, int, ll, int, int, int)':
dishes.cpp:46:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
upd(a, b, d, m + 1, r, n << 1 + 1);
~~^~~
dishes.cpp:47:49: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
tree[n] = max(tree[n << 1], tree[n << 1 + 1]);
~~^~~
dishes.cpp: In member function 'void BIT::upd2(int, ll, int, int, int)':
dishes.cpp:58:37: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
upd2(x, v, m + 1, r, n << 1 + 1);
~~^~~
dishes.cpp:59:49: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
tree[n] = max(tree[n << 1], tree[n << 1 + 1]);
~~^~~
dishes.cpp: In member function 'll BIT::quer(int, int, int, int, int)':
dishes.cpp:67:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
ll R = quer(a, b, m + 1, r, n << 1 + 1);
~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:145:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj2[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:170:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj1[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:218:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj2[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
617 ms |
287756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
94460 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94556 KB |
Output is correct |
| 3 |
Incorrect |
97 ms |
94584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
94460 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94556 KB |
Output is correct |
| 3 |
Incorrect |
97 ms |
94584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
94460 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94556 KB |
Output is correct |
| 3 |
Incorrect |
97 ms |
94584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
94460 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94556 KB |
Output is correct |
| 3 |
Incorrect |
97 ms |
94584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
94460 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94556 KB |
Output is correct |
| 3 |
Incorrect |
97 ms |
94584 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
617 ms |
287756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
617 ms |
287756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
