#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
#define X first
#define Y second
#define pb push_back
typedef long double ld;
#define MAXN 1001001
int n, m, nn = 1 << 20;
ll a[MAXN], s[MAXN], p[MAXN];
ll b[MAXN], u[MAXN], k[MAXN];
vector<ii> x[MAXN];
ll ap[MAXN], bp[MAXN];
ll t[4 * MAXN];
ll pd[4 * MAXN], pm[4 * MAXN];
void propaj(int cv)
{
t[cv] += pd[cv];
t[cv] = max(t[cv], pm[cv]);
pd[cv * 2] += pd[cv];
pd[cv * 2 + 1] += pd[cv];
pm[cv * 2] += pm[cv];
pm[cv * 2 + 1] += pm[cv];
pd[cv] = pm[cv] = 0;
}
void dodaj(int cv, int lo, int hi, int l, int r, ll h)
{
propaj(cv);
if (lo > hi || lo > r || hi < r || l > r) return;
if (lo >= l && hi <= r) {
pd[cv] += h;
pm[cv] += h;
return;
}
int mid = (lo + hi) / 2;
dodaj(cv * 2, lo, mid, l, r, h);
dodaj(cv * 2 + 1, mid + 1, hi, l, r, h);
}
void maxaj(int cv, int lo, int hi, int l, int r, ll h)
{
propaj(cv);
if (lo > hi || lo > r || hi < r || l > r) return;
if (lo >= l && hi <= r) {
pm[cv] = max(pm[cv], h);
return;
}
int mid = (lo + hi) / 2;
maxaj(cv * 2, lo, mid, l, r, h);
maxaj(cv * 2 + 1, mid + 1, hi, l, r, h);
}
ll kveri(int cv, int lo, int hi, int h)
{
propaj(cv);
if (lo == hi) {
return t[cv];
}
int mid = (lo + hi) / 2;
if (h <= mid)
return kveri(cv * 2, lo, mid, h);
else
return kveri(cv * 2 + 1, mid + 1, hi, h);
}
ll reza = 0LL;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
ap[i + 1] = a[i] + (i ? a[i - 1] : 0);
}
for (int i = 0; i < m; i++) {
scanf("%lld%lld%lld", &b[i], &u[i], &k[i]);
bp[i + 1] = b[i] + (i ? b[i - 1] : 0);
}
for (int i = 0; i < n; i++) {
x[i].pb({upper_bound(bp, bp + m + 1, (s[i] - ap[i + 1])) - bp, p[i]});
}
for (int i = 0; i < m; i++) {
ll izraz = upper_bound(ap, ap + n + 1, (u[i] - bp[i + 1])) - ap - 1;
if (izraz)
x[izraz].pb({i + 1, -k[i]});
reza += k[i];
}
for (int i = 0; i <= n; i++) {
for (ii j: x[i]) {
//cout << i << ' ' << j.X << ' ' << j.Y << endl;
dodaj(1, 0, nn - 1, 0, j.X - 1, j.Y);
}
for (ii j: x[i]) {
if (j.X)
maxaj(1, 0, nn - 1, j.X, m, kveri(1, 0, nn - 1, j.X - 1));
}
}
printf("%lld\n", reza + kveri(1, 0, nn - 1, m));
return 0;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:87:9: 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], &p[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &b[i], &u[i], &k[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
61896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
61896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
61896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
