#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;
int N, M;
ll A[MAXN+10], S[MAXN+10], P[MAXN+10];
ll B[MAXN+10], T[MAXN+10], Q[MAXN+10];
ll ans;
struct Point
{
int x, y; ll w;
};
vector<Point> V;
ll tree[MAXN*4+10];
bool lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
if(!lazy[node]) return;
tree[node]=0;
if(tl!=tr) lazy[node*2]=true, lazy[node*2+1]=true;
lazy[node]=false;
}
ll query(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}
void update1(int node, int tl, int tr, int p, ll v)
{
busy(node, tl, tr);
if(tr<p) return;
if(tl==tr)
{
tree[node]+=v;
return;
}
int mid=tl+tr>>1;
if(p<=mid) update1(node*2, tl, mid, p, v);
else update1(node*2+1, mid+1, tr, p, v);
tree[node]=tree[node*2]+tree[node*2+1];
}
void update2(int node, int tl, int tr, int l, int r)
{
if(r<l) return;
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]=true;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update2(node*2, tl, mid, l, r);
update2(node*2+1, mid+1, tr, l, r);
tree[node]=tree[node*2]+tree[node*2+1];
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];
for(i=1; i<=N; i++)
{
if(A[i]>S[i]) continue;
int x=i, y=upper_bound(B+1, B+M+1, S[i]-A[i])-B-1;
ans+=P[i];
if(y!=M)
{
x--; y++;
V.push_back({x, y, -P[i]});
}
}
for(i=1; i<=M; i++)
{
if(B[i]>T[i]) continue;
int y=i, x=upper_bound(A+1, A+N+1, T[i]-B[i])-A-1;
if(x!=N && y!=M) V.push_back({x, y, Q[i]});
else ans+=Q[i];
}
//printf("ANS %lld\n", ans);
sort(V.begin(), V.end(), [&](const Point &p, const Point &q)
{
if(p.x!=q.x) return p.x<q.x;
if(p.y!=q.y) return p.y>q.y;
return p.w>q.w;
});
//for(i=0; i<V.size(); i++) printf("%d %d %lld\n", V[i].x, V[i].y, V[i].w);
if(V.empty()) return !printf("%lld\n", ans);
for(i=0; i<V.size(); i++)
{
//printf("!%d %d %lld\n", V[i].x, V[i].y, V[i].w);
int y=V[i].y; ll w=V[i].w;
if(w>=0)
{
update1(1, 0, M, y, w);
}
else
{
int lo=0, hi=M+1;
ll t=query(1, 0, M, 0, y-1)-w;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(query(1, 0, M, 0, mid)<=t) lo=mid;
else hi=mid;
}
//printf("U2 %d %d\n", y, lo);
ll p=query(1, 0, M, 0, hi), q=query(1, 0, M, hi, hi);
update2(1, 0, M, y, lo);
update1(1, 0, M, hi, -q+p-t);
}
for(j=1; j<=M; j++) assert(query(1, 0, M, 0, j-1)<=query(1, 0, M, 0, j));
//printf("\n");
}
ans+=query(1, 0, M, 0, M);
printf("%lld\n", ans);
}
Compilation message
dishes.cpp: In function 'll query(int, int, int, int, int)':
dishes.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'void update1(int, int, int, int, ll)':
dishes.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'void update2(int, int, int, int, int)':
dishes.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:115:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V.size(); i++)
~^~~~~~~~~
dishes.cpp:130:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=lo+hi>>1;
~~^~~
dishes.cpp:77: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:78:64: 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]), A[i]+=A[i-1];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
dishes.cpp:79:64: 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]), B[i]+=B[i-1];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
18148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
18148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10088 ms |
18148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
