thegscrypto.bot
Evidence
Lots of WA1/RE1/Compilation Error submissions
AI commented codes: 375834481 375825486 375825486. Mostly all of his submission are like this
Harshaii
Evidence
AI commented codes: 375846083 375846083
gopal.thecoder
Evidence
375836893... bruh
(if you can't view this submission, here's the code)
Spoiler
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);
}
}
}
```
f20240621
Evidence
C2 submission: 375822058, D submission: 375824904, AI commented and different coding style
Bitrelica
Evidence
Change of style in 375799863 375800768 and 375813042. Impossible contest timing: (28:26 -> 29:47 -> 31:23 -> 37:17 -> 40:25...)
Comment other cheaters in the comments (include evidence too) :)



