Problem: steadfastsnakes (2017 round3)

Once upon a time, you were the proud owner of a great many ladders and snakes.
Unfortunately, you were forced to give up all but one of each, and in time,
even your single remaining snake slithered away...

But all of that is about to change. You've just received word that a new
executive order has been passed which will allow you to once again keep as
many snakes as you'd like! To prepare, you've eagerly gone ahead and
constructed a series of **N** ladders which will serve as a home for the
impending flock of snakes. Unfortunately, it was only then that you realized
your huge mistake — feeding snakes is extraordinarily expensive!

The **N** ladders are arranged in a line on the ground, with each one standing
up vertically. Each pair of consecutive ladders are 1 metre apart from each
other, and the _i_th ladder from the left initially has a height of **Hi**
metres. As an expert in reptilian behavioral patterns, you're sure that a
certain number of snakes will soon arrive on your property. In particular,
every possible unordered pair of ladders will surely be claimed by a single
snake, meaning that exactly **N** * (**N** \- 1) / 2 snakes will be showing
up. If a snake claims the pair of ladders _i_ and _j_, it will want to stretch
itself out perfectly between the tops of those two ladders, such that its body
runs down one ladder, along the ground, and up along the other ladder.
Therefore, such a snake will surely have a length of exactly **Hi** \+ |_j_ \-
_i_| + **Hj** metres.

You're desperate to reduce the heights of some of your ladders as quickly as
possible so as to attract some shorter snakes and save your wallet. You
estimate that you've got **K** minutes to make your alterations before the
snakes start showing up. Each minute, you may choose a single ladder and cut
off its top few rungs, reducing its height by exactly 1 metre. You may not
shorten a ladder if it's already only 1 metre tall. You may choose not to cut
any ladders in a given minute.

As everyone knows, the daily cost of feeding a snake is proportional to its
length. That being said, you're not concerned with the total amount you'll
have to dish out every day, but rather on the largest amount you'll have to
spend on any one snake. As such, you're like to determine the minimum possible
length that the _longest_ of the **N** * (**N** \- 1) / 2 snakes can end up
having, given that you perform your ladder cutting optimally.

You're given **H1**, and **H2..N** may then be calculated as follows using
given constants **A**, **B**, and **C**.

**Hi** = ((**A** * **Hi-1** \+ **B**) %**C** \+ 1 

### Input

Input begins with an integer **T**, the number of different sets of ladders.
For each set of ladders, there is first a line containing the space-separated
integers **N** and **K**. Then there is a line with four space-separated
integers, **H1**, **A**, **B** and **C**.

### Output

For the _i_th snake, print a line containing "Case #**i**: " followed by the
minimum possible length that the longest snake can have (in metres).

### Constraints

1 ≤ **T** ≤ 20  
2 ≤ **N** ≤ 800,000  
0 ≤ **K** ≤ 1015  
1 ≤ **H1**, **C** ≤ 1,000,000,000  
0 ≤ **A**, **B** ≤ 1,000,000,000  

### Explanation of Sample

In the first case the ladders have heights of 4, 5, and 6 metres respectively.
Cutting the last ladder 3 times will yields height of 4, 5, and 3. The longest
snake is then the one which claims the first two ladders, with a length of 4 +
1 + 5 = 10 metres. You could instead cut the second ladder once and the third
ladder twice for final heights of 4, 4, and 4. In this case, the longest snake
is the one which claims the first and last ladders, with a length of 4 + 2 + 4
= 10 metres.

In the second case, you have more than enough time to trim all of the ladders
down to a height of 1 metre each. The longest snake is then the one which
claims the first and last ladders, with a length of 1 + 4 + 1 = 6 metres.

In the third case, the ladder heights are [6, 16, 36, 2, 8, 20, 7, 18].



Sample input:
5
3 3
4 1 0 100
5 100
1 2 3 4
8 8
6 2 3 37
1000 30000
10 10 10 1337
25000 888888
987 654 321 123456789


Sample output:
Case #1: 10
Case #2: 6
Case #3: 51
Case #4: 2692
Case #5: 246727827



Code: // Hacker Cup 2017
// Round 3
// Steadfast Snakes
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 800008

int L[2];
LL BLT[2][2][LIM];

void Update(int a,int b,int i,int v)
{
	for(i++;i<=L[a];i+=(i&-i))
		BLT[a][b][i]+=v;
}

LL Query(int a,int b,int i)
{
	LL v=0;
		for(i++;i>0;i-=(i&-i))
			v+=BLT[a][b][i];
	return(v);
}

int main()
{
	// vars
	int T,t;
	int N,A,B,C;
	LL K;
	int i,j,c,v,ans;
	int r1,r2,m;
	LL s;
	static int H[LIM];
	static int n1,n2,c1[LIM],c2[LIM],v1[LIM],v2[LIM],vc1[LIM],vc2[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			scanf("%d%lld",&N,&K);
			Read(v),Read(A),Read(B),Read(C);
				Fox(i,N)
				{
					H[i]=v;
					v=((LL)A*v+B)%C+1;
				}
			// check if there's a single dominating ladder
			j=0;
				Fox(i,N)
					if (H[i]>H[j])
						j=i;
				Fox(i,N)
					if ((i!=j) && (H[i]>H[j]-K-abs(i-j)))
						break;
				if (i==N)
				{
					// special case - only shorten the dominating ladder
					ans=0;
						Fox(i,N)
							if (i!=j)
								Max(ans,H[j]-(int)K+H[i]+abs(i-j));
					goto Done;
				}
			// compress diagonal coordinates
			n1=n2=0;
				Fox(i,N)
				{
					c1[n1++]=v1[i]=i-H[i];
					c2[n2++]=v2[i]=-i-H[i];
				}
			sort(c1,c1+n1);
			sort(c2,c2+n2);
			L[0]=n1=unique(c1,c1+n1)-c1;
			L[1]=n2=unique(c2,c2+n2)-c2;
				Fox(i,N)
				{
					vc1[i]=lower_bound(c1,c1+n1,v1[i])-c1;
					vc2[i]=lower_bound(c2,c2+n2,v2[i])-c2;
				}
			// init BLTs
			Fill(BLT,0);
				Fox(i,N)
				{
					Update(1,0,vc2[i],1);
					Update(1,1,vc2[i],v2[i]);
				}
			// try every possible pyramid center x-coordinate
			ans=2*INF+N;
				Fox(i,N)
				{
					// move ladder i from right to left BLT
					Update(0,0,vc1[i],1);
					Update(0,1,vc1[i],v1[i]);
					Update(1,0,vc2[i],-1);
					Update(1,1,vc2[i],-v2[i]);
					// centered on i
					r1=max(i+1,N-i),r2=INF+N;
						while (r2>=r1)
						{
							m=(r1+r2)>>1;
							// left
							v=i-m;
							c=lower_bound(c1,c1+n1,v)-c1-1;
							s=Query(0,0,c)*v-Query(0,1,c);
							// right
							v=-i-m;
							c=lower_bound(c2,c2+n2,v)-c2-1;
							s+=Query(1,0,c)*v-Query(1,1,c);
								if (s<=K)
									r2=m-1,Min(ans,2*m);
								else
									r1=m+1;
						}
					// centered on i+0.5
						if (i==N-1)
							break;
					r1=max(i+1,N-i-1),r2=INF+N;
						while (r2>=r1)
						{
							m=(r1+r2)>>1;
							// left
							v=i-m;
							c=lower_bound(c1,c1+n1,v)-c1-1;
							s=Query(0,0,c)*v-Query(0,1,c);
							// right
							v=-(i+1)-m;
							c=lower_bound(c2,c2+n2,v)-c2-1;
							s+=Query(1,0,c)*v-Query(1,1,c);
								if (s<=K)
									r2=m-1,Min(ans,2*m+1);
								else
									r1=m+1;
						}
				}
Done:;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}