#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fenwick{
ll T[1010101];
ll m;
void init(ll _m) { m = _m; }
void addval(ll p, ll v)
{
if(!p) T[0] += v;
else{
for(; p<=m; p+=p&-p){
T[p] += v;
}
}
}
ll getval(ll p)
{
ll ret = T[0];
for(; p; p-=p&-p){
ret += T[p];
}
return ret;
}
};
ll A[1010101], S[1010101], P1[1010101], P2[1010101];
ll B[1010101], T[1010101], Q1[1010101], Q2[1010101];
vector <ll> V[1010101];
set <ll> X;
fenwick F;
ll n, m, ans;
void query(ll f, ll p, ll k)
{
ll x;
if(f == 0) F.addval(0, k);
else if(f == 1){
if(X.find(p) == X.end()) X.insert(p);
F.addval(p, k);
return;
}
else if(f == 2){
if(X.find(p) == X.end()) X.insert(p);
F.addval(p, k);
}
for(; ; ){
auto it = X.upper_bound(p);
if(it == X.end()) break;
x = F.getval(*it) - F.getval(*it - 1) - Q1[*it];
if(x <= k){
F.addval(*it, -x); k -= x;
X.erase(it);
}
else{
F.addval(*it, -k);
break;
}
}
}
int main()
{
ll i, k, x;
scanf("%lld%lld", &n, &m);
for(i=1; i<=n; i++){
scanf("%lld%lld%lld", A + i, S + i, P1 + i);
A[i] += A[i - 1];
if(P1[i] < 0){
ans += P1[i];
P2[i] = -P1[i], P1[i] = 0;
}
}
for(i=1; i<=m; i++){
scanf("%lld%lld%lld", B + i, T + i, Q1 + i);
B[i] += B[i - 1];
if(Q1[i] < 0){
ans += Q1[i];
Q2[i] = -Q1[i], Q1[i] = 0;
}
}
for(i=1; i<=n; i++){
S[i] = upper_bound(B, B + m + 1, S[i] - A[i]) - B;
}
for(i=1; i<=m; i++){
T[i] = upper_bound(A, A + n + 1, T[i] - B[i]) - A;
V[T[i]].push_back(i);
}
F.init(m);
for(i=1; i<=m; i++){
if(T[i] == 0) swap(Q1[i], Q2[i]);
F.addval(i, Q1[i]);
}
for(i=1; i<=n; i++){
for(ll &t: V[i]){
swap(Q1[t], Q2[t]);
if(Q1[t] == 0){
if(X.find(t) == X.end()) X.insert(t);
}
else{
if(X.find(t) == X.end()){
query(2, t, Q1[t]);
}
else{
x = F.getval(t) - F.getval(t - 1);
if(x <= Q1[t]){
X.erase(t);
query(2, t, Q1[t] - x);
}
}
}
}
if(S[i] == 0) ans += P2[i];
else if(S[i] > m) ans += P1[i];
else{
if(P2[i] == 0) query(0, S[i] - 1, P1[i]);
else query(1, S[i], P2[i]);
}
}
for(ll &t: V[n + 1]){
ans += Q1[t];
}
printf("%lld\n", F.getval(m) + ans);
return 0;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:76:8: warning: unused variable 'k' [-Wunused-variable]
ll i, k, x;
^
dishes.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~
dishes.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", A + i, S + i, P1 + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", B + i, T + i, Q1 + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
50032 KB |
Output is correct |
| 2 |
Incorrect |
306 ms |
41272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
24088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
24088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
24088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
24088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
24088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
50032 KB |
Output is correct |
| 2 |
Incorrect |
306 ms |
41272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
50032 KB |
Output is correct |
| 2 |
Incorrect |
306 ms |
41272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
