#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 = 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();
if (s != e){
l->prop();
r->prop();
v = max(l->v, r->v);
}
//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;
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];
if (Ta+1 <= m) 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:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
101 | main(){
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:114:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
114 | printf("A row %d needs col <= %d\n",i,Ta);
| ~^ ~
| | |
| int long long int
| %lld
dishes.cpp:114:40: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
114 | printf("A row %d needs col <= %d\n",i,Ta);
| ~^ ~~
| | |
| int long long int
| %lld
dishes.cpp:118:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
118 | printf("%d %d +%d\n",i,0,p[i]);
| ~^ ~
| | |
| int long long int
| %lld
dishes.cpp:118:29: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
118 | printf("%d %d +%d\n",i,0,p[i]);
| ~^ ~~~~
| | |
| int long long int
| %lld
dishes.cpp:119:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
119 | printf("%d %d -%d\n",i,Ta+1,p[i]);
| ~^ ~
| | |
| int long long int
| %lld
dishes.cpp:119:25: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
119 | printf("%d %d -%d\n",i,Ta+1,p[i]);
| ~^ ~~~~
| | |
| int long long int
| %lld
dishes.cpp:119:29: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
119 | printf("%d %d -%d\n",i,Ta+1,p[i]);
| ~^ ~~~~
| | |
| int long long int
| %lld
dishes.cpp:162:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
162 | printf("%d ",root->qu(i));
| ~^ ~~~~~~~~~~~
| | |
| int long long int
| %lld
dishes.cpp:133:9: warning: unused variable 'ans' [-Wunused-variable]
133 | int ans = 0;
| ^~~
dishes.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%lld%lld%lld",&b[i],&t[i],&q[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10104 ms |
605880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10104 ms |
605880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10104 ms |
605880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
