#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;
const llong INF = 1e18;
int n, m;
template <typename T>
struct Fenwick
{
T tree[MAXN];
void update(int pos, T val)
{
for (int idx = pos ; idx <= m ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
T query(int pos)
{
T res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
int findKthZero(int k)
{
int idx = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (idx + (1 << log) <= m && (1 << log) - tree[idx + (1 << log)] < k)
{
idx += (1 << log);
k -= (1 << log) - tree[idx];
}
}
return idx + 1;
}
int findKthOne(int k)
{
int idx = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (idx + (1 << log) <= m && tree[idx + (1 << log)] < k)
{
idx += (1 << log);
k -= tree[idx];
}
}
return idx + 1;
}
};
struct SegmentTree
{
struct Node
{
llong value;
llong lazy;
Node()
{
value = lazy;
}
};
Node tree[4*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].value = (l == m + 1 ? 0LL : -INF);
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
}
void push(int node, int l, int r)
{
if (tree[node].lazy == 0)
{
return;
}
if (tree[node].value != -INF) tree[node].value += tree[node].lazy;
if (l < r)
{
tree[2*node].lazy += tree[node].lazy;
tree[2*node + 1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
void rangeUpdate(int l, int r, int node, int queryL, int queryR, int queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy = queryVal;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
rangeUpdate(l, mid, 2*node, queryL, queryR, queryVal);
rangeUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
}
void setUpdate(int l, int r, int node, int queryPos, llong queryVal)
{
push(node, l, r);
if (queryPos < l || r < queryPos)
{
return;
}
if (l == r)
{
tree[node].value = queryVal;
return;
}
int mid = (l + r) / 2;
setUpdate(l, mid, 2*node, queryPos, queryVal);
setUpdate(mid + 1, r, 2*node + 1, queryPos, queryVal);
}
llong query(int l, int r, int node, int queryPos)
{
push(node, l, r);
if (l == r)
{
return tree[node].value;
}
int mid = (l + r) / 2;
if (queryPos <= mid) return query(l, mid, 2*node, queryPos);
else return query(mid + 1, r, 2*node + 1, queryPos);
}
void build()
{
build(1, m + 1, 1);
}
void update(int pos, llong value)
{
setUpdate(1, m + 1, 1, pos, value);
}
void rangeUpdate(int l, int r, int value)
{
rangeUpdate(1, m + 1, 1, l, r, value);
}
llong query(int pos)
{
return query(1, m + 1, 1, pos);
}
};
Fenwick <int> fenwickNext;
Fenwick <llong> fenwickActive;
SegmentTree dp;
struct Dish
{
int time;
llong limit;
int reward;
int idx;
bool type;
};
Dish a[MAXN];
Dish b[MAXN];
llong prefixA[MAXN];
llong prefixB[MAXN];
bool isNext[MAXN];
bool isActive[MAXN];
llong dpBorderM[MAXN];
llong active[MAXN];
int globalRow;
llong findValue(int col)
{
if (col == m + 1)
{
return dp.query(m + 1);
}
int cnt = col - 1 - fenwickNext.query(col - 1);
int pos = m;
if (cnt != m - fenwickNext.query(m))
{
pos = fenwickNext.findKthZero(cnt + 1);
}
return fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp.query(pos);
}
void fix(int col)
{
assert(col <= m);
llong curr = dp.query(col);
llong next = findValue(col + 1) + active[col];
int res = isNext[col];
fenwickNext.update(col, -res);
int nextVal = 0;
isNext[col] = false;
if (curr < next)
{
nextVal = 1;
isNext[col] = true;
fenwickNext.update(col, 1);
}
dp.update(col, std::max(curr, next));
if (col > 1)
{
int queryRes = fenwickNext.query(col - 1);
if (queryRes < col - 1)
{
int cntZeroesToNow = col - 1 - queryRes;
int pos = fenwickNext.findKthZero(cntZeroesToNow);
llong nextVal = findValue(pos + 1) + active[pos];
if (nextVal > findValue(pos)) fix(pos);
}
if (queryRes > 0)
{
int cntOnesToNow = queryRes;
int pos = fenwickNext.findKthOne(cntOnesToNow);
llong nextVal = findValue(pos + 1) + active[pos];
if (nextVal > findValue(pos)) fix(pos);
}
}
}
void applyUpdate(int to, int val)
{
dp.rangeUpdate(1, to, val);
}
std::vector <int> activateAt[MAXN];
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
prefixA[i] = prefixA[i - 1] + a[i].time;
}
for (int i = 1 ; i <= m ; ++i)
{
prefixB[i] = prefixB[i - 1] + b[i].time;
}
for (int aPos = n ; aPos >= 1 ; --aPos)
{
dpBorderM[aPos] = dpBorderM[aPos + 1] + (prefixA[aPos - 1] + prefixB[m] + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0);
}
for (int i = 1 ; i <= m ; ++i)
{
int l = 0, r = n + 2, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (prefixA[mid - 1] + prefixB[i] <= b[i].limit) l = mid;
else r = mid;
}
activateAt[l].push_back(i);
}
globalRow = n + 1;
for (int i = 1 ; i <= m ; ++i)
{
fenwickNext.update(i, 1);
isNext[i] = true;
}
std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ());
dp.build();
for (const int &idx : activateAt[globalRow])
{
active[idx] = b[idx].reward;
fenwickActive.update(idx, b[idx].reward);
fix(idx);
}
for (int i = 1 ; i <= m ; ++i)
{
dp.update(i, findValue(i));
}
// for (int i = 1 ; i <= m + 1 ; ++i)
// {
// std::cout << findValue(i) << ' ';
// }
// std::cout << '\n';
for (globalRow = n ; globalRow >= 1 ; --globalRow)
{
for (const int &idx : activateAt[globalRow])
{
dp.update(idx, findValue(idx));
}
int l = 0, r = m + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (prefixA[globalRow] + prefixB[mid - 1] <= a[globalRow].limit) l = mid;
else r = mid;
}
if (l > 0)
{
dp.update(l, findValue(l));
}
for (const int &idx : activateAt[globalRow])
{
active[idx] = b[idx].reward;
fenwickActive.update(idx, b[idx].reward);
}
if (l > 0) activateAt[globalRow].push_back(l);
applyUpdate(l, a[globalRow].reward);
dp.update(m + 1, dpBorderM[globalRow]);
activateAt[globalRow].push_back(m);
std::sort(activateAt[globalRow].begin(), activateAt[globalRow].end(), std::greater <int> ());
for (const int &idx : activateAt[globalRow])
{
fix(idx);
}
// for (int i = 1 ; i <= m ; ++i) fix(i);
// for (int i = 1 ; i <= m + 1 ; ++i)
// {
// std::cout << findValue(i) << ' ';
// }
// std::cout << '\n';
}
globalRow++;
std::cout << findValue(1) << '\n';
}
void input()
{
std::cin >> n >> m;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i].time >> a[i].limit >> a[i].reward;
a[i].idx = i;
a[i].type = false;
}
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> b[i].time >> b[i].limit >> b[i].reward;
b[i].idx = i;
a[i].type = true;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
signed main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
dishes.cpp: In function 'void fix(int)':
dishes.cpp:236:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
236 | int nextVal = 0;
| ^~~~~~~
dishes.cpp: In constructor 'SegmentTree::Node::Node()':
dishes.cpp:79:21: warning: '*<unknown>.SegmentTree::Node::lazy' is used uninitialized in this function [-Wuninitialized]
79 | value = lazy;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
778 ms |
121040 KB |
Output is correct |
| 2 |
Incorrect |
781 ms |
122252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
94036 KB |
Output is correct |
| 2 |
Correct |
39 ms |
93904 KB |
Output is correct |
| 3 |
Correct |
39 ms |
93924 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
93836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
94036 KB |
Output is correct |
| 2 |
Correct |
39 ms |
93904 KB |
Output is correct |
| 3 |
Correct |
39 ms |
93924 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
93836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
94036 KB |
Output is correct |
| 2 |
Correct |
39 ms |
93904 KB |
Output is correct |
| 3 |
Correct |
39 ms |
93924 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
93836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
94036 KB |
Output is correct |
| 2 |
Correct |
39 ms |
93904 KB |
Output is correct |
| 3 |
Correct |
39 ms |
93924 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
93836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
94036 KB |
Output is correct |
| 2 |
Correct |
39 ms |
93904 KB |
Output is correct |
| 3 |
Correct |
39 ms |
93924 KB |
Output is correct |
| 4 |
Incorrect |
39 ms |
93836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
778 ms |
121040 KB |
Output is correct |
| 2 |
Incorrect |
781 ms |
122252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
778 ms |
121040 KB |
Output is correct |
| 2 |
Incorrect |
781 ms |
122252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
