I completely understand how frustrating that is! My previous fix strictly resolved the C# compilation error (the variable naming conflict) so your code could finally compile and run, but it left your underlying mathematical logic untouched.
Now that the code is executing, the "Wrong Answer" is exposing a very subtle **sign error** in your Convex Hull Trick query for the left side (`tr2`).
### The Math Behind the Bug
For the right side (`tr1`), you want to maximize the score. Mathematically, the expression you are optimizing for index $$$i$$$ is:
<center>$$$s[i] - s[m] - (i - m) \cdot h[m]$$$</center>
Which expands and groups to:
<center>$$$(s[i]) - (h[m]) \cdot i - s[m] + m \cdot h[m]$$$</center>
Your `Query` function evaluates $$$y - M \cdot x$$$. For `tr1`, $$$y = s[i]$$$, $$$x = i$$$, and you correctly pass $$$M = h[m]$$$. This flawlessly matches the equation.
**However, for the left side (`tr2`)**, you want to maximize the score going backwards. That expression is:
<center>$$$s[m-1] - s[i-1] - (m - i) \cdot h[m]$$$</center>
Let's expand and group this one:
<center>$$$(-s[i-1]) + h[m] \cdot i + s[m-1] - m \cdot h[m]$$$</center>
Notice the **$$$+ h[m] \cdot i$$$**.
Since your `Query` function subtracts the slope term ($$$y - M \cdot x$$$), to get a positive $$$h[m] \cdot i$$$, you **must** pass $$$-h[m]$$$ as the slope. In your code, you passed a positive `h[m]`:
```csharp
// WRONG
long mxvl = tr2.Query(1, 1, n, a2, b2, h[m]) + s[m - 1] - (long)m * h[m];
```
This forces the tree to evaluate $$$-s[i-1] - h[m] \cdot i$$$, which completely breaks the calculation and underestimates the score.
### The Fix
Change `h[m]` to `-h[m]` in the `tr2.Query` call.
Here is the fully corrected code with the mathematical fix applied.
```csharp
// Author => Gopal
using System;
using System.IO;
#pragma warning disable CS8618
class GRoadworks
{
struct Point
{
public long x, y;
}
class ConvexHST
{
private Point[] hull;
private int[] hullst;
private int[] hullln;
private int hulllptr;
public ConvexHST(int n)
{
hull = new Point[n * 20];
hullst = new int[4 * n + 5];
hullln = new int[4 * n + 5];
}
public void clear()
{
hulllptr = 0;
}
private bool Bad(Point a, Point b, Point c)
{
Int128 dx1 = b.x - a.x;
Int128 dy1 = b.y - a.y;
Int128 dx2 = c.x - a.x;
Int128 dy2 = c.y - a.y;
return dx1 * dy2 - dy1 * dx2 >= 0;
}
public void build(int nd, int l, int r, long[] x, long[] y)
{
hullst[nd] = hulllptr;
int len = 0;
int strt = hulllptr;
for (int i = l; i <= r; i++)
{
Point p = new Point { x = x[i], y = y[i] };
while (len >= 2)
{
Point a = hull[strt + len - 2];
Point b = hull[strt + len - 1];
if (Bad(a, b, p)) len--;
else break;
}
hull[strt + len] = p;
len++;
}
hullln[nd] = len;
hulllptr += len;
if (l == r) return;
int mid = l + (r-l) / 2;
build(2 * nd, l, mid, x, y);
build(2 * nd + 1, mid + 1, r, x, y);
}
public long Query(int nd, int l, int r, int ql, int qr, long m)
{
if (ql <= l && r <= qr)
{
int lt = 0, rt = hullln[nd] - 1;
int strt = hullst[nd];
while (lt < rt)
{
int mid = lt + (rt - lt) / 2;
Point p1 = hull[strt + mid];
Point p2 = hull[strt + mid + 1];
if (p2.y - p1.y >= m * (p2.x - p1.x)) lt = mid + 1;
else rt = mid;
}
return hull[strt + lt].y - m * hull[strt + lt].x;
}
int mdidx = l + (r - l) / 2;
long res = long.MinValue;
if (ql <= mdidx) res = Math.Max(res, Query(2 * nd, l, mdidx, ql, qr, m));
if (qr > mdidx) res = Math.Max(res, Query(2 * nd + 1, mdidx + 1, r, ql, qr, m));
return res;
}
}
class FastIO
{
private Stream s;
private byte[] buf = new byte[1 << 20];
private int pos, len;
public FastIO(Stream strm) { s = strm; }
private int NextChar()
{
if (pos >= len)
{
pos = 0;
len = s.Read(buf, 0, buf.Length);
if (len == 0) return -1;
}
return buf[pos++];
}
public long NextLong()
{
int c = NextChar();
while (c != -1 && c <= 32) c = NextChar();
if (c == -1) return 0;
long res = 0;
while (c > 32)
{
res = res * 10 + (c - '0');
c = NextChar();
}
return res;
}
public int NextInt() => (int)NextLong();
}
static void Main()
{
using var strm = new BufferedStream(Console.OpenStandardInput(), 1 << 20);
FastIO io = new FastIO(strm);
using var wrt = new StreamWriter(Console.OpenStandardOutput(), bufferSize: 1 << 20);
int t = io.NextInt();
if (t == 0) return;
int mxn = 200005;
long[] h = new long[mxn];
long[] d = new long[mxn];
long[] e = new long[mxn];
long[] pe = new long[mxn];
long[] s = new long[mxn];
long[] xs = new long[mxn];
long[] y1 = new long[mxn];
long[] y2 = new long[mxn];
ConvexHST tr1 = new ConvexHST(mxn);
ConvexHST tr2 = new ConvexHST(mxn);
while (t-- > 0)
{
int n = io.NextInt();
long k = io.NextLong();
int x = io.NextInt();
for (int i = 1; i <= n; i++) h[i] = io.NextLong();
for (int i = 1; i < n; i++) d[i] = io.NextLong();
e[x] = 0;
for (int i = x + 1; i <= n; i++) e[i] = Math.Max(e[i - 1] + 1, d[i - 1]);
for (int i = x - 1; i >= 1; i--) e[i] = Math.Max(e[i + 1] + 1, d[i]);
int lmx = x, rmx = x;
while (lmx > 1 && e[lmx - 1] <= k) lmx--;
while (rmx < n && e[rmx + 1] <= k) rmx++;
pe[x] = 0;
long crmx = h[x];
for (int i = x + 1; i <= n; i++)
{
if (e[i] > k) break;
long w = e[i] - e[i-1] - 1;
pe[i] = pe[i-1] + h[i] + w * crmx;
crmx = Math.Max(crmx, h[i]);
}
crmx = h[x];
for (int i = x - 1; i >= 1; i--)
{
if (e[i] > k) break;
long w = e[i] - e[i + 1] - 1;
pe[i] = pe[i + 1] + h[i] + w * crmx;
crmx = Math.Max(crmx, h[i]);
}
s[0] = 0;
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + h[i];
xs[i] = i;
y1[i] = s[i];
y2[i] = -s[i - 1];
}
tr1.clear();
tr1.build(1, 1, n, xs, y1);
tr2.clear();
tr2.build(1, 1, n, xs, y2);
long ans = 0;
for (int m = 1; m <= n; m++)
{
if (e[m] > k) continue;
long bsscr = pe[m] + (k - e[m]) * h[m];
int a1 = m;
int b1 = (int)Math.Min(rmx, m + k - e[m]);
if (a1 <= b1)
{
long mxvl = tr1.Query(1, 1, n, a1, b1, h[m]) - s[m] + (long)m * h[m];
ans = Math.Max(ans, bsscr + mxvl);
}
int a2 = (int)Math.Max(lmx, m - (k - e[m]));
int b2 = m;
if (a2 <= b2)
{
long mxvl = tr2.Query(1, 1, n, a2, b2, -h[m]) + s[m - 1] - (long)m * h[m];
ans = Math.Max(ans, bsscr + mxvl);
}
}
wrt.WriteLine(ans);
}
}
}
```