#include "closing.h"
#include <vector>
#include <utility>
#include <map>
std::vector<std::pair<int, int>> down[200020];
std::vector<std::pair<long long, int>> build(int N, int X)
{
std::multimap<long long, int> map = {};
std::vector<bool> f(N);
std::vector<std::pair<long long, int>> ans = {};
f[X] = true;
map.insert(std::make_pair(0LL, X));
long long sum = 0;
while (map.size() > 0)
{
std::multimap<long long, int>::iterator it = map.lower_bound(-1);
long long w = it->first;
int ii = it->second;
map.erase(it);
sum += w;
ans.push_back(std::make_pair(sum, 1 + ans.size()));
for (size_t i = 0; i < down[ii].size(); i++)
{
if (!f[down[ii][i].first])
{
f[down[ii][i].first] = true;
map.insert(std::make_pair(w + down[ii][i].second, down[ii][i].first));
}
}
}
return ans;
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for (int i = 0; i < N; i++)
{
down[i].clear();
}
bool lin = true;
for (size_t i = 0; i < W.size(); i++)
{
int a = U[i];
int b = V[i];
if (a == i && b == i + 1 || b == i && a == i + 1)
{
}
else
{
lin = false;
}
down[a].push_back(std::make_pair(b, W[i]));
down[b].push_back(std::make_pair(a, W[i]));
}
std::vector<std::pair<long long, int>> dx = build(N, X);
std::vector<std::pair<long long, int>> dy = build(N, Y);
int ans = 0;
for (size_t i = 0; i < dy.size(); i++)
{
if (dy[i].first > K)
break;
ans = std::max(ans, dy[i].second);
}
int iy = dy.size() - 1;
for (size_t i = 0; i < dx.size(); i++)
{
if (dx[i].first > K)
break;
while (iy >= 0 && dx[i].first + dy[iy].first > K)
{
iy--;
}
if (iy >= 0)
ans = std::max(ans, dx[i].second + dy[iy].second);
else
ans = std::max(ans, dx[i].second);
}
if (lin)
{
long long sx = 0;
long long sy = 0;
int x = X;
int y = Y;
long long sum = 0;
std::vector<int> WW(N);
int count = 2;
while (x < y - 1)
{
if (sx + W[x] < sy + W[y - 1])
{
sum += sx + W[x];
sx += W[x];
x++;
WW[x] = sx;
count++;
}
else
{
sum += sy + W[y - 1];
sy += W[y - 1];
y--;
WW[y] = sy;
count++;
}
}
if (sum <= K)
{
std::vector <bool> first(N);
std::vector<std::pair<long long, std::pair<int, int>>> sec(N);
std::multimap<long long, std::pair<int, int>> map = {};
if (X > 0)
{
map.insert(std::make_pair(0LL + W[X - 1], std::make_pair(X - 1, -1)));
first[X - 1] = true;
}
map.insert(std::make_pair(sx + W[x] - WW[x + 1], std::make_pair(x + 1, 1)));
first[x] = true;
if (Y + 1 < N)
{
map.insert(std::make_pair(0LL + W[Y], std::make_pair(Y + 1, 1)));
first[Y + 1] = true;
}
map.insert(std::make_pair(sy + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
first[y] = true;
while (map.size() > 0)
{
std::multimap<long long, std::pair<int, int>>::iterator it = map.lower_bound(-1);
long long w = it->first;
std::pair<int, int> ii = it->second;
map.erase(it);
sum += w;
if (sum > K)
{
break;
}
if (ii.second == 1)
{
x = ii.first;
w += WW[x];
WW[x] = w;
first[x] = false;
if (sec[x].first != 0)
{
map.insert(std::make_pair(sec[x].first - WW[x], sec[x].second));
sec[x].first = 0;
}
if (x + 1 < N)
{
if (!first[x + 1])
{
map.insert(std::make_pair(w + W[x] - WW[x + 1], std::make_pair(x + 1, 1)));
first[x + 1] = true;
}
else
{
sec[x + 1] = std::make_pair(w + W[x], std::make_pair(x + 1, 1));
}
}
}
else
{
y = ii.first;
w += WW[y];
WW[y] = w;
first[y] = false;
if (sec[y].first != 0)
{
map.insert(std::make_pair(sec[y].first - WW[y], sec[y].second));
sec[y].first = 0;
}
if (y > 0)
{
if (!first[y - 1])
{
map.insert(std::make_pair(w + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
first[y - 1] = true;
}
else
{
sec[y - 1] = (std::make_pair(w + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
}
}
}
count++;
}
ans = std::max(ans, count);
}
}
return ans;
}
