#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
const ll INF = 1e18;
int N, M;
ll A[MAXN+10], S[MAXN+10], P[MAXN+10];
ll B[MAXN+10], T[MAXN+10], Q[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
ll ans;
struct Point
{
int x, y; ll val;
bool operator < (const Point &p)
{
if(x==p.x) return y>p.y;
return x<p.x;
}
};
vector<Point> V;
ll tree[MAXN*4+10], maxv[MAXN*4+10], add[MAXN*4+10];
void busy(int node, int tl, int tr)
{
tree[node]=max(maxv[node], tree[node])+add[node];
if(tl!=tr)
{
ll a, b, c, d;
a=maxv[node*2], b=add[node*2], c=maxv[node], d=add[node];
c-=b; swap(b, c);
maxv[node*2]=max(a, b); add[node*2]=c+d;
a=maxv[node*2+1], b=add[node*2+1], c=maxv[node], d=add[node];
c-=b; swap(b, c);
maxv[node*2+1]=max(a, b); add[node*2+1]=c+d;
}
add[node]=0; maxv[node]=-INF;
}
void update1(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
maxv[node]=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update1(node*2, tl, mid, l, r, k);
update1(node*2+1, mid+1, tr, l, r, max(tree[node*2], k));
tree[node]=max(tree[node*2], tree[node*2+1]);
}
void update2(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
add[node]=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update2(node*2, tl, mid, l, r, k);
update2(node*2+1, mid+1, tr, l, r, k);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
ll query(int node, int tl, int tr, int pos)
{
busy(node, tl, tr);
if(tl==tr) return tree[node];
int mid=tl+tr>>1;
if(pos<=mid) return query(node*2, tl, mid, pos);
else return query(node*2+1, mid+1, tr, pos);
}
int main()
{
int i, j, k;
scanf("%d%d", &N, &M);
for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);
for(i=1; i<=N; i++) A[i]+=A[i-1];
for(i=1; i<=M; i++) B[i]+=B[i-1];
for(i=1; i<=N; i++) X[i]=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
for(i=1; i<=M; i++) Y[i]=upper_bound(A, A+N+1, T[i]-B[i])-A-1;
for(i=1; i<=N; i++) ans+=P[i];
for(i=1; i<=N; i++) if(X[i]+1<=M) V.push_back({i-1, X[i]+1, -P[i]});
for(i=1; i<=M; i++) if(Y[i]>=0) V.push_back({Y[i], i, Q[i]});
sort(V.begin(), V.end());
for(j=0; j<V.size(); j++)
{
if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
Point it=V[j];
//D[0]=C[0]; for(i=1; i<=M; i++) D[i]=max(D[i-1], C[i]);
//for(i=it.y; i<=M; i++) C[i]=D[i]+it.val;
update1(1, 1, M, it.y, M, -INF);
update2(1, 1, M, it.y, M, it.val);
}
ans+=query(1, 1, M, M);
printf("%lld\n", ans);
}
Compilation message
dishes.cpp: In function 'void update1(int, int, int, int, int, ll)':
dishes.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'void update2(int, int, int, int, int, ll)':
dishes.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'll query(int, int, int, int)':
dishes.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<V.size(); j++)
~^~~~~~~~~
dishes.cpp:110:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
~~~^~~~~~~~~
dishes.cpp:90:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
dishes.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:93:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:94:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
514 ms |
33488 KB |
Output is correct |
2 |
Correct |
507 ms |
40404 KB |
Output is correct |
3 |
Correct |
403 ms |
37724 KB |
Output is correct |
4 |
Correct |
384 ms |
34640 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
467 ms |
39248 KB |
Output is correct |
7 |
Correct |
275 ms |
26820 KB |
Output is correct |
8 |
Correct |
128 ms |
12792 KB |
Output is correct |
9 |
Correct |
406 ms |
37724 KB |
Output is correct |
10 |
Correct |
430 ms |
37584 KB |
Output is correct |
11 |
Correct |
344 ms |
34652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
514 ms |
33488 KB |
Output is correct |
2 |
Correct |
507 ms |
40404 KB |
Output is correct |
3 |
Correct |
403 ms |
37724 KB |
Output is correct |
4 |
Correct |
384 ms |
34640 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
467 ms |
39248 KB |
Output is correct |
7 |
Correct |
275 ms |
26820 KB |
Output is correct |
8 |
Correct |
128 ms |
12792 KB |
Output is correct |
9 |
Correct |
406 ms |
37724 KB |
Output is correct |
10 |
Correct |
430 ms |
37584 KB |
Output is correct |
11 |
Correct |
344 ms |
34652 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
514 ms |
33488 KB |
Output is correct |
2 |
Correct |
507 ms |
40404 KB |
Output is correct |
3 |
Correct |
403 ms |
37724 KB |
Output is correct |
4 |
Correct |
384 ms |
34640 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
467 ms |
39248 KB |
Output is correct |
7 |
Correct |
275 ms |
26820 KB |
Output is correct |
8 |
Correct |
128 ms |
12792 KB |
Output is correct |
9 |
Correct |
406 ms |
37724 KB |
Output is correct |
10 |
Correct |
430 ms |
37584 KB |
Output is correct |
11 |
Correct |
344 ms |
34652 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |