#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000000000000;
int n,m;
int a[200005], s[200005], p[200005];
int b[200005], t[200005], q[200005];
int pa[200005], pb[200005];
map<int, int> M[200005];
struct node{
int s,e,m,v;
int la, lu, marked;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s+e)/2;
v = 0;
la = lu = 0;
if (s != e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void prop(){
if (marked){
v = lu;
if (s != e){
l->lu = lu;
r->lu = lu;
l->marked = r->marked = true;
l->la = r->la = 0;
}
marked = lu = 0;
}
if (la){
v += la;
if (s != e){
l->la += la;
r->la += la;
}
la = 0;
}
}
void SET(int qs, int qe, int nv){
prop();
if (qs == s && qe == e){
marked = true;
lu = nv;
la = 0;
return;
}
if (qs > m) r->SET(qs,qe,nv);
else if (qe <= m) l->SET(qs,qe,nv);
else{
l->SET(qs,m,nv);
r->SET(m+1,qe,nv);
}
l->prop();
r->prop();
v = max(l->v, r->v);
}
void ADD(int qs, int qe, int nv){
prop();
if (qs == s && qe == e){
la += nv;
return;
}
if (qs > m) r->ADD(qs,qe,nv);
else if (qe <= m) l->ADD(qs,qe,nv);
else{
l->ADD(qs,m,nv);
r->ADD(m+1,qe,nv);
}
l->prop();
r->prop();
v = max(l->v, r->v);
}
int qu(int x){
prop();
if (s == e) return v;
if (x > m) return r->qu(x);
else return l->qu(x);
}
int fin(int x){
prop();
//printf("finding first element > %d, cur %d %d\n",x,s,e);
if (s == e) {
if (v <= x) return e+1;
else return e;
}
if (l->v > x) return l->fin(x);
else return r->fin(x);
}
} *root;
void update(int l, int r, int v){
if (v == 0) return;
if (l == 0){
//printf("ADDING %d %d to %d\n",l,r,v);
return;
}
int val = root->qu(l-1);
int ID2 = max(l, min(r+1, root->fin(val-v)));
//printf("ID2 = %d: finding %d: --> %d\n",ID2, val-v, root->fin(val-v));
if (l <= ID2-1){
root->SET(l, ID2-1, val);
//printf("SETTING %d %d to %d\n",l,ID2-1,val);
}
if (ID2 <= r){
//printf("ADDING %d %d to %d\n",ID2,r,v);
}
}
main(){
scanf("%lld%lld",&n,&m);
for (int i = 1; i <= n; i++){
scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
pa[i] = pa[i-1] + a[i];
}
for (int i = 1; i <= m; i++){
scanf("%lld%lld%lld",&b[i],&t[i],&q[i]);
pb[i] = pb[i-1] + b[i];
}
for (int i = 1; i <= n; i++){
int Ta = upper_bound(pb, pb+m+1, s[i]-pa[i])-pb-1;
//printf("A row %d needs col <= %d\n",i,Ta);
if (Ta != -1) {
M[i][0] += p[i];
M[i][Ta+1] -= p[i];
//printf("%d %d +%d\n",i,0,p[i]);
//printf("%d %d -%d\n",i,Ta+1,p[i]);
}
}
for (int i = 1; i <= m; i++){
int Tb = upper_bound(pa, pa+n+1, t[i]-pb[i])-pa-1;
//printf("B col %d needs row <= %d\n",i,Tb);
if (Tb != -1) {
M[Tb+1][i] += q[i];
//printf("%d %d +%d\n",Tb+1,i,q[i]);
}
}
root = new node(0, m);
int ans = 0;
for (int i = 0; i <= n+1; i++){
//printf("at %d\n",i);
for (auto it = M[i].rbegin(); it != M[i].rend(); it++){
int id, v;
tie(id,v) = *it;
//printf("updating %d %d %d\n",id,m,v);
root->ADD(id, m, v);
}
//for (int i = 0; i <= m; i++){
// printf("%d ",root->qu(i));
//}
//printf("\n");
for (auto it = M[i].begin(); it != M[i].end(); it++){
int id, v;
tie(id,v) = *it;
if (id) {
int val = root->qu(id-1);
int id2 = root->fin(val)-1;
//printf("id1 = %d, id2 = %d, setting to %d\n",id,id2,val);
if (id2 < id) continue;
root->SET(id, id2, val);
}
}
//for (int i = 0; i <= m; i++){
// printf("%d ",root->qu(i));
//}
//printf("\n");
}
printf("%lld\n",root->qu(m));
}
Compilation message
dishes.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
116 | main(){
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:148:9: warning: unused variable 'ans' [-Wunused-variable]
148 | int ans = 0;
| ^~~
dishes.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%lld%lld%lld",&b[i],&t[i],&q[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
79796 KB |
Output is correct |
| 2 |
Runtime error |
291 ms |
167676 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
79796 KB |
Output is correct |
| 2 |
Runtime error |
291 ms |
167676 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
79796 KB |
Output is correct |
| 2 |
Runtime error |
291 ms |
167676 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
