#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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];
int X[maxn], Y[maxn], inv[maxn], pnt[maxn];
vector<int> adj1[maxn], adj2[maxn];
ll dp[maxn];
ll offset;
struct BIT {
vector<ll> tree, lazy;
void init() {
tree = vector<ll>(4 * N, -1e17);
lazy = vector<ll>(4 * N, 0);
}
void prop(int l, int r, int n) {
if(l != r) {
tree[2*n] += lazy[n];
lazy[2*n] += lazy[n];
tree[2*n + 1] += lazy[n];
lazy[2*n + 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, 2*n);
upd(a, b, d, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 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, 2*n);
upd2(x, v, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 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, 2*n);
ll R = quer(a, b, m + 1, r, 2*n + 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() {
freopen("in.txt", "r", stdin);
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];
//*
vector<ll> nA, nB, nS, nT, nP, nQ;
for(int i = 0; i < N; i++) {
if(P[i] >= 0) {
nA.push_back(A[i]);
nS.push_back(S[i]);
nP.push_back(P[i]);
}
else {
nA.push_back(A[i]);
nS.push_back(S[i]);
nP.push_back(0);
}
for(int j = 0; j < adj2[i].size(); j++) {
int k = adj2[i][j];
if(Q[k] < 0) {
nA.push_back(A[i]);
nS.push_back(A[i] + B[k] - 1);
nP.push_back(-Q[k]);
}
}
}
for(int i = 0; i < M; i++) {
if(Q[i] >= 0) {
nB.push_back(B[i]);
nT.push_back(T[i]);
nQ.push_back(Q[i]);
}
else {
nB.push_back(B[i]);
nT.push_back(T[i]);
nQ.push_back(0);
}
for(int j = 0; j < adj1[i].size(); j++) {
int k = adj1[i][j];
if(P[k] < 0) {
nB.push_back(B[i]);
nT.push_back(B[i] + A[k] - 1);
nQ.push_back(-P[k]);
}
}
}
N = nA.size();
M = nB.size();
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();
//*/
vector<pii> ord;
for(int i = 0; i < N; i++) ord.push_back(pii(X[i], -i));
sort(ord.begin(), ord.end());
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]);
//cout << dp[i] << endl;
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);
cout << ans + offset;
}
Compilation message
dishes.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
dishes.cpp: In function 'int main()':
dishes.cpp:144:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj2[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:166:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj1[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:217:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj2[i].size(); j++) {
~~^~~~~~~~~~~~~~~~
dishes.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("in.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:113: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:116: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:119: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 |
Incorrect |
99 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
94200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
