#include "fish.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#pragma GCC optimize ("Ofast,fast-math")
#pragma GCC target ("sse4")
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;
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];
std::vector <llong> minusIN[MAXM];
std::vector <llong> minusL[MAXM];
std::vector <llong> LR[MAXM];
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;
}
}
llong max = 0;
for (int x = n ; x >= 1 ; --x)
{
if (x + 3 <= n)
{
for (const Position &curr : pos[x + 3])
{
max = std::max(max, dp[curr.idx][0] + curr.left + curr.right);
}
}
for (int type = 0 ; type < 2 ; ++type)
{
for (const Position &curr : pos[x])
{
if (x == n)
{
continue;
}
dp[curr.idx][type] = max;
int l = -1, r = pos[x + 1].size(), mid;
while (l < r - 1)
{
mid = (l + r) >> 1;
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[x + 1][l]);
}
if (r < pos[x + 1].size() && type == 0)
{
dp[curr.idx][type] = std::max(dp[curr.idx][type], LR[x + 1][r] - curr.in - curr.right);
}
if (x + 2 <= n)
{
l = -1;
r = pos[x + 2].size();
while (l < r - 1)
{
mid = (l + r) >> 1;
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[x + 2][l]);
}
if (r < pos[x + 2].size())
{
dp[curr.idx][type] = std::max(dp[curr.idx][type], LR[x + 2][r] - curr.right);
}
}
}
}
LR[x].reserve(pos[x].size());
minusL[x].reserve(pos[x].size());
minusIN[x].reserve(pos[x].size());
for (const Position &curr : pos[x])
{
minusIN[x].push_back(dp[curr.idx][1] - curr.in + curr.right);
LR[x].push_back(dp[curr.idx][0] + curr.left + curr.right);
minusL[x].push_back(dp[curr.idx][0] + curr.right);
}
for (int i = 1 ; i < pos[x].size() ; ++i)
{
minusIN[x][i] = std::max(minusIN[x][i - 1], minusIN[x][i]);
minusL[x][i] = std::max(minusIN[x][i - 1], minusL[x][i]);
}
for (int i = (int)pos[x].size() - 2 ; i >= 0 ; --i)
{
LR[x][i] = std::max(LR[x][i], LR[x][i + 1]);
}
}
for (int x = std::min(n, 3) ; x >= 1 ; --x)
{
for (const Position &curr : pos[x])
{
max = std::max(max, dp[curr.idx][0] + curr.left + curr.right);
}
}
return max;
}
