#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 _in, llong _left, llong _right)
{
y = _y;
idx = _idx;
left = _left;
right = _right;
in = _in;
}
};
int cnt;
struct SegmentTree
{
llong tree[1 << 20];
SegmentTree()
{
std::fill(tree, tree + 1 << 20, (llong)-1e18);
}
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][2];
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)
{
std::sort(fish[x].begin(), fish[x].end());
for (const auto &[y, w] : fish[x])
{
if (x != 1)
{
posUncleared[x - 1].push_back({y, 0, 0LL, 0LL, 0LL});
}
if (x != n)
{
posUncleared[x + 1].push_back({y, 0, 0LL, 0LL, 0LL});
}
}
}
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;
}
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 = 1 ; x <= n ; ++x)
{
for (Position &p : pos[x])
{
p.idx = ++cnt;
}
}
for (int x = n ; x >= 1 ; --x)
{
for (int type = 0 ; type < 2 ; ++type)
{
for (const Position &curr : pos[x])
{
if (x == n) 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][type] = std::max(dp[curr.idx][type], minusIN.query(pos[x + 1][0].idx, pos[x + 1][l].idx));
}
if (r < pos[x + 1].size() && type == 0)
{
dp[curr.idx][type] = std::max(dp[curr.idx][type], 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][type] = std::max(dp[curr.idx][type], minusL.query(pos[x + 2][0].idx, pos[x + 2][l].idx));
}
if (r < pos[x + 2].size())
{
dp[curr.idx][type] = std::max(dp[curr.idx][type], LR.query(pos[x + 2][r].idx, pos[x + 2].back().idx) - curr.right);
}
}
int firstIdx = pos[x].back().idx + 1;
if (x + 1 <= n && !pos[x + 1].empty())
{
firstIdx = pos[x + 1].back().idx + 1;
}
if (x + 2 <= n && !pos[x + 2].empty())
{
firstIdx = pos[x + 2].back().idx + 1;
}
if (firstIdx <= cnt)
{
dp[curr.idx][type] = std::max(dp[curr.idx][type], LR.query(firstIdx, cnt));
}
}
for (const Position &curr : pos[x])
{
minusIN.update(curr.idx, dp[curr.idx][1] - curr.in + curr.right);
LR.update(curr.idx, dp[curr.idx][0] + curr.left + curr.right);
minusL.update(curr.idx, dp[curr.idx][0] + curr.right);
}
}
}
return LR.query(1, cnt);
}
Compilation message
fish.cpp: In constructor 'SegmentTree::SegmentTree()':
fish.cpp:36:34: error: invalid operands of types 'llong*' {aka 'long long int*'} and 'int' to binary 'operator<<'
36 | std::fill(tree, tree + 1 << 20, (llong)-1e18);
| ~~~~~~~~ ^~ ~~
| | |
| | int
| llong* {aka long long int*}
fish.cpp:36:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
36 | std::fill(tree, tree + 1 << 20, (llong)-1e18);
| ~~~~~^~~
fish.cpp: In function 'llong max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:135: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]
135 | while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:141: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]
141 | while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:147: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]
147 | while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
| ~~~~~~^~~~~~~~~~~~~~~~
fish.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | if (r < pos[x + 1].size() && type == 0)
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:208:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
208 | if (r < pos[x + 2].size())
| ~~^~~~~~~~~~~~~~~~~~~
