#include "fish.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 600000 + 10;
struct Position
{
int y;
int idx;
llong in;
llong left;
llong right;
Position(int _y, int _idx, llong _left, llong _right)
{
y = _y;
idx = _idx;
left = _left;
right = _right;
}
};
int cnt;
struct SegmentTree
{
llong tree[4*MAXM];
void update(int l, int r, int node, int queryIdx, llong value)
{
if (l == r)
{
tree[node] = value;
return;
}
int mid = (l + r) / 2;
if (queryIdx <= mid) update(l, mid, 2*node, queryIdx, value);
else update(mid + 1, r, 2*node + 1, queryIdx, value);
tree[node] = std::max(tree[2*node], tree[2*node + 1]);
}
llong query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
llong ans = -1e18;
int mid = (l + r) / 2;
if (queryL <= mid) ans = std::max(ans, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) ans = std::max(ans, query(mid + 1, r, 2*node + 1, queryL, queryR));
return ans;
}
void update(int pos, llong value)
{
update(1, cnt, 1, pos, value);
}
llong query(int l, int r)
{
return query(1, cnt, 1, l, r);
}
};
int n, m;
llong dp[MAXM];
std::vector <Position> pos[MAXN];
std::vector <Position> posUncleared[MAXN];
std::vector <std::pair <int,int>> fish[MAXN];
SegmentTree LR, minusL, minusIN;
llong max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
n = N; m = M;
for (int i = 0 ; i < m ; ++i)
{
fish[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
}
for (int x = 1 ; x <= n ; ++x)
{
for (const auto &[y, w] : fish[x])
{
if (x != 1)
{
assert(y != 1);
posUncleared[x - 1].push_back({y, 0, 0LL, 0LL});
}
if (x != n)
{
assert(y != 1);
posUncleared[x + 1].push_back({y, 0, 0LL, 0LL});
}
}
}
return 0;
for (int x = 1 ; x <= n ; ++x)
{
std::sort(posUncleared[x].begin(), posUncleared[x].end(), [&](Position a, Position b)
{
return a.y < b.y;
});
for (Position p : posUncleared[x])
{
if (!pos[x].empty() && pos[x].back().y == p.y)
{
continue;
}
p.idx = ++cnt;
pos[x].push_back(p);
}
int ptrL = 0;
int ptrR = 0;
int ptrIN = 0;
llong inSum = 0;
llong leftSum = 0;
llong rightSum = 0;
for (Position &p : pos[x])
{
while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
{
leftSum += fish[x - 1][ptrL].second;
ptrL++;
}
while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
{
rightSum += fish[x + 1][ptrR].second;
ptrR++;
}
while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
{
inSum += fish[x][ptrIN].second;
ptrIN++;
}
p.in = inSum;
p.left = leftSum;
p.right = rightSum;
}
}
for (int x = n ; x >= 1 ; --x)
{
for (const Position &curr : pos[x])
{
if (x == n)
{
LR.update(curr.idx, dp[curr.idx] + curr.left + curr.right);
minusL.update(curr.idx, dp[curr.idx] - curr.left + curr.right);
minusIN.update(curr.idx, dp[curr.idx] - curr.in + curr.right);
continue;
}
int l = -1, r = pos[x + 1].size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (pos[x + 1][mid].y < curr.y) l = mid;
else r = mid;
}
if (l >= 0)
{
dp[curr.idx] = std::max(dp[curr.idx], minusIN.query(pos[x + 1][0].idx, pos[x + 1][l].idx));
}
if (r < pos[x + 1].size())
{
dp[curr.idx] = std::max(dp[curr.idx], LR.query(pos[x + 1][r].idx, pos[x + 1].back().idx) - curr.in - curr.right);
}
if (x + 2 <= n)
{
l = -1;
r = pos[x + 2].size();
while (l < r - 1)
{
mid = (l + r) / 2;
if (pos[x + 2][mid].y < curr.y) l = mid;
else r = mid;
}
if (l >= 0)
{
dp[curr.idx] = std::max(dp[curr.idx], minusL.query(pos[x + 2][0].idx, pos[x + 2][l].idx));
}
if (r < pos[x + 2].size())
{
dp[curr.idx] = std::max(dp[curr.idx], LR.query(pos[x + 2][r].idx, pos[x + 2].back().idx) - curr.right);
}
}
int firstIdx = pos[x].back().idx + 1;
if (!pos[x + 1].empty())
{
firstIdx = pos[x + 1].back().idx + 1;
}
if (!pos[x + 2].empty())
{
firstIdx = pos[x + 2].back().idx + 1;
}
if (firstIdx <= cnt)
{
dp[curr.idx] = std::max(dp[curr.idx], LR.query(firstIdx, cnt));
}
LR.update(curr.idx, dp[curr.idx] + curr.left + curr.right);
minusL.update(curr.idx, dp[curr.idx] - curr.left + curr.right);
minusIN.update(curr.idx, dp[curr.idx] - curr.in + curr.right);
}
}
return LR.query(1, cnt);
}
Compilation message
fish.cpp: In function 'llong max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:132:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:138:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
| ~~~~~~^~~~~~~~~~~~~~~~
fish.cpp:181:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | if (r < pos[x + 1].size())
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | if (r < pos[x + 2].size())
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
22840 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14712 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
22840 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
