#include <bits/stdc++.h>
using namespace std;
#define int long long
///segtree store amt can move right before die
///query rightmost num below bval
///shift B there (range dec everything to the right)
///if B gains a point then win, else try displace 1 as well
const int INF = 999999999999999999LL;
///range min
struct node{
int s,e,v;
int lazy;
node *l,*r;
node (int _s, int _e){
s = _s; e = _e;
if (s==e){
v = INF;
}
else{
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
v = min(l->v,r->v);
}
}
void proc(){
if (lazy==0) return;
v += lazy;
if (s!=e){
l->lazy += lazy;
r->lazy += lazy;
}
lazy = 0;
}
int descR(int val){
proc();
if (v>=val) return -1;
if (s==e) return s;
if (r->v<val) return r->descR(val);
return l->descR(val);
}
void upd(int a, int b, int val){
if (b<a) return;
proc();
if (a<=s && e<=b){
lazy += val;
proc();
return;
}
if (b<=(s+e)/2){
l->upd(a,b,val);
}
else if (a>(s+e)/2){
r->upd(a,b,val);
}
else {
l->upd(a,b,val);
r->upd(a,b,val);
}
l->proc();r->proc();
v = min(l->v,r->v);
}
}*root;
int n,m;
int A[1000005];
int S[1000005];
int P[1000005];
int B[1000005];
int T[1000005];
int Q[1000005];
int prefA[1000005];
int prefB[1000005];
main(){
scanf("%lld%lld",&n,&m);
for (int x = 0; x<n; x++){
scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
}
for (int x = 0; x<m; x++){
scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
}
root = new node(0,n-1);
for (int x = 1; x<=n; x++){
prefA[x] = prefA[x-1]+A[x-1];
}
for (int x = 1; x<=m; x++){
prefB[x] = prefB[x-1]+B[x-1];
}
int ans = 0;
for (int x = 0; x<n; x++){
if (prefA[x+1]<=S[x]){
ans++;
root->upd(x,x,-INF+S[x]-prefA[x+1]);
}
}
int Bans = 0;
int minv = -1;
for (int x = 0; x<m; x++){
int t = B[x];
int t2 = root->descR(t);
if (prefA[t2+1]+prefB[x+1]<=T[x]){
t2 = max(t2,minv);
Bans++;
minv = t2;
root->upd(t2+1,n-1,-B[x]);
}
else{
root->upd(t2,t2,INF);
int t3 = root->descR(t);
root->upd(t2,t2,-INF);
if (prefA[t3+1]+prefB[x+1]<=T[x] && minv<t2){
t3 = max(t3,minv);
minv = t3;
root->upd(t3+1,n-1,-B[x]);
root->upd(t2,t2,INF);
}
else{
t2 = max(t2,minv);
minv = t2;
root->upd(t2+1,n-1,-B[x]);
}
}
}
printf("%lld",ans+Bans);
}
Compilation message
dishes.cpp:79:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main(){
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
37912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
37912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
37912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
