I tried to submit some code onto oj.uz but I received Failed verdict. I'm convinced the problem is not surrounding me but surrounding the server because these two submissions are identical but one passed and one also received Failed verdict.

https://oj.uz/submission/311279

https://oj.uz/submission/318735

Does anybody know what is going on? Is oj.uz down? When will the "Failed" submissions be rejudged?

UPD: It seems like the problem is fixed. On a general note, the "Failed" verdict may occur due to a problem with the server.

Can I have a hint for https://dmoj.ca/problem/ccoprep2p2?

What is the time complexity? How should I sweep triangles? I think I need to use $$$x,y,d\le 10^6$$$

Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4)

This dp satisfies the property $$$dp[j]=max_{i<j} (dp[i]+C[i][j])$$$, where $$$C[i][j]$$$ satisfies quadrangle inequality. How can I optimize to O(n log n) or O(n)?

Outline: since all queries are sorted in ascending order, I can do it with convex hull and binary search (if k=3). This gives O(n log n).

How binary search is done:

Fix $$$i<k<j$$$, we compare $$$dp[i]+C[i][j]$$$ with $$$dp[k]+C[k][j]$$$

Note $$$C[i][j]=(prefix[j]-prefix[i])^{\frac{k}{2}}$$$. It grows faster than $$$C[k][j]$$$. In fact, $$$(prefix[j]-prefix[i])-(prefix[j]-prefix[k])$$$ is an invariant, call $$$x$$$. Let $$$y=dp[k]-dp[i]$$$. Rewrite $$$C[k][j]=z, C[i][j]=z+x$$$.

Consider $$$(a,b)$$$ such that $$$a^{\frac{3}{2}}-b^{\frac{3}{2}}=y$$$, and $$$a-b=x$$$. The precise solution would use sqrt, and would take O(log n) anyways (to an error of $$$10^{-6}$$$, might raise if TLE). (Am I wrong?) Note $$$a$$$ corresponds to $$$C[i][j]$$$ and $$$b$$$ corresponds to $$$C[k][j]$$$, even though they might never be equal to those values. Then for all $$$C[i][j]>a$$$, $$$dp[i]+C[i][j]>dp[k]+C[k][j]$$$ and for all $$$C[i][j]<a$$$, $$$dp[i]+C[i][j]<dp[k]+C[k][j]$$$

Is this correct? Implementation looks rly hard.