| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 701585 | boris_mihov | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[4*MAXM];
SegmentTree()
{
std::fill(tree, tree + 4*MAXM, (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[2], minusL[2], minusIN[2];
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());
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 (int type = 0 ; type < 2 ; ++type)
{
for (const Position &curr : pos[x])
{
if (x == n)
{
minusL[type].update(curr.idx, dp[curr.idx][type] - curr.left + curr.right);
minusIN[type].update(curr.idx, dp[curr.idx][type] - curr.in + curr.right);
LR[type].update(curr.idx, dp[curr.idx][type] + curr.left + 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][type] = std::max(dp[curr.idx][type], minusIN[1].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[0].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[0].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[0].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][type] = std::max(dp[curr.idx][type], LR[0].query(firstIdx, cnt));
}
minusL[type].update(curr.idx, dp[curr.idx][type] - curr.left + curr.right);
minusIN[type].update(curr.idx, dp[curr.idx][type] - curr.in + curr.right);
LR[type].update(curr.idx, dp[curr.idx][type] + curr.left + curr.right);
}
}
}
return LR[0].query(1, cnt);
}