Problem: fossil_fuels (2018 round2)

The Earth is gripped by an energy crisis. There's simply not enough to go
around! Desperate to unlock additional sources of energy, James has decided to
direct his attention downwards. Perhaps enough fossils can be found
underground and harvested for just a bit more fuel?

James has surveyed a linear stretch of ground, and has fortunately discovered
**N** fossils beneath the surface! From a cross-sectional view, the _i_th
fossil is at position **Pi** metres along the stretch of ground, at a depth of
**Di** metres below the surface. No two fossils are in exactly the same spot
(at both the same position and depth).

The next question is, of course, how the fossils might be unearthed most
efficiently. James plans to dig one or more vertical mine shafts in order to
access all **N** fossils. A mine shaft is defined by a position _p_ and a
depth _d_. Such a mine shaft can be represented as a vertical line segment at
position _p_ metres along the stretch of ground, running from the surface to a
point _d_ metres below the surface. James can dig such a shaft at a cost of
**S** \+ _d_ dollars, where **S** is a constant. Once it has been dug, it's
possible to reach fossils from the shaft by descending to the correct depth
and then digging horizontally through the earth at no additional cost, up to a
distance of at most **M** metres away from the shaft, where **M** is another
constant. In other words, each fossil _i_ is accessible from the shaft if
**Di** ≤ _d_ and |**Pi** \- _p_| ≤ **M**. Note that a mine shaft is permitted
to pass directly through a fossil (such that _p_ = **Pi** for some _i_).

Help James determine the minimum total cost of mine shafts which he must dig,
such that each of the **N** fossils will end up being accessible from at least
one of the shafts.

In order to reduce the size of the input data, the sequences **P1..N** and
**D1..N** will be derived from a series of temporary sequences **A1..(2*K)**,
the _i_th of of which has a length of **Li**. **P1..N** can be constructed by
concatenating together **A1..K**, while **D1..N** can be constructed by
concatenating together **A(K+1)..(2*K)**. It's guaranteed that the sum of
**L1..K** is equal to **N**, as is the sum of **L(K+1)..(2*K)**. For each
sequence **Ai**, you're given **Ai,1**, and **Ai,2..Li** may then be generated
as follows using given constants **Xi**, **Yi**, and **Zi** (please watch out
for integer overflow during this process):

**Ai,j** = ((**Xi** * **Ai,j-1** \+ **Yi**) % **Zi**) + 1 (for _j_ = 2..**Li**) 

### Input

Input begins with an integer **T**, the number of sets of fossils. For each
set of fossils, there is first a line containing the space-separated integers
**N**, **S**, **M**, and **K**. Then, 2 * **K** lines follow. The _i_th of
these contains the space-separated integers **Li**, **Ai,1**, **Xi**, **Yi**,
and **Zi**.

### Output

For the _i_th set of fossils, output a line containing "Case #_i_: " followed
by the minimum total cost of mine shafts which James must dig (in dollars).

### Constraints

1 ≤ **T** ≤ 40  
1 ≤ **N** ≤ 1,000,000  
0 ≤ **S**, **M** ≤ 1,000,000,000  
1 ≤ **K** ≤ 10  
1 ≤ **Pi**, **Di**, **Ai,j** ≤ 1,000,000,000  
1 ≤ **Li** ≤ **N**  
0 ≤ **Xi**, **Yi** < **Zi** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, **P** = [5, 25] and **D** = [3, 4]. James should dig a
single mine shaft with _p_ = 15 and _d_ = 4 (at a cost of 5 + 4 = 9 dollars),
from which both fossils are barely accessible.

In the second case, **P** = [5, 26] and **D** = [3, 4]. James now requires two
mine shafts (for example one with _p_ = 5 and _d_ = 3 and another with _p_ =
26 and _d_ = 4), at a total cost of (5 + 3) + (5 + 4) = 17 dollars.

In the third case, **P** = [27, 11, 19, 15, 67] and **D** = [41, 34, 67, 40,
53].

In the fourth case, **P** = [555, 776, 673, 654, 339, 832, 887, 370, 555,
3794, 334, 180, 2491, 2018, 2805, 2 427, 1986, 3138, 1149, 495] and **D** =
[20814, 20463, 40527, 38076, 18468, 10958, 25830, 23128, 28505, 10884, 32935,
116 66, 8264, 771, 1207, 8930, 1299, 8521, 7277, 7440].



Sample input:
5
2 5 10 2
1 5 0 0 100
1 25 0 0 100
1 3 0 0 100
1 4 0 0 100
2 5 10 2
1 5 0 0 100
1 26 0 0 100
1 3 0 0 100
1 4 0 0 100
5 10 5 1
5 27 62 36 100
5 41 81 12 100
20 0 555 3
8 555 731 1056 1234
5 555 3829 309 4321
7 2018 927 1931 3333
5 20814 27645 39785 54321
7 10958 3958 20298 33333
8 8264 11938 6378 12345
763720 129808360 12754053 1
763720 64542433 21197820 117877269 258961984
763720 138453872 151021996 102071067 196497793


Sample output:
Case #1: 9
Case #2: 17
Case #3: 190
Case #4: 60341
Case #5: 3589308654



Code: // Fossil Fuels
// Solution by Jacob Plachta

#define DEBUG 0

#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); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

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

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

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 2100000

int N,S,M;
int sz;
LL treeD[LIM],treeS[LIM];
int lazyM[LIM];

void Prop(int i)
{
	int m=lazyM[i];
		if (m)
		{
			lazyM[i]=0;
			treeS[i]=treeD[i]+m;
				if (i<sz)
				{
					i<<=1;
					lazyM[i]=lazyM[i+1]=m;
				}
		}
}

void UpdateD(int i,int r1,int r2,int a,LL d)
{
	Prop(i);
		if ((r1==a) && (r2==a))
		{
			treeD[i]=d;
			return;
		}
	int m=(r1+r2)>>1;
	int c=i<<1;
		if (a<=m)
			UpdateD(c,r1,m,a,d);
		else
			UpdateD(c+1,m+1,r2,a,d);
	Prop(c),Prop(c+1);
	treeD[i]=min(treeD[c],treeD[c+1]);
	treeS[i]=min(treeS[c],treeS[c+1]);
}

void UpdateM(int i,int r1,int r2,int a,int b,int mm)
{
	Prop(i);
		if ((a<=r1) && (r2<=b))
		{
			lazyM[i]=mm;
			Prop(i);
			return;
		}
	int m=(r1+r2)>>1;
	int c=i<<1;
		if (a<=m)
			UpdateM(c,r1,m,a,b,mm);
		if (b>m)
			UpdateM(c+1,m+1,r2,a,b,mm);
	Prop(c),Prop(c+1);
	treeS[i]=min(treeS[c],treeS[c+1]);
}

LL QueryS(int i,int r1,int r2,int a,int b)
{
	Prop(i);
		if ((a<=r1) && (r2<=b))
			return(treeS[i]);
	LL ret=(LL)INF*INF;
	int m=(r1+r2)>>1;
	int c=i<<1;
		if (a<=m)
			Min(ret,QueryS(c,r1,m,a,b));
		if (b>m)
			Min(ret,QueryS(c+1,m+1,r2,a,b));
	return(ret);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int K,L,A,X,Y,Z;
	int i,j,k,m;
	LL d;
	static PR P[LIM];
	static LL dyn[LIM];
	stack<int> MD;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(S),Read(M),Read(K);
			k=0;
				Fox(i,K*2)
				{
						if (i==K)
							k=0;
					Read(L),Read(A),Read(X),Read(Y),Read(Z);
						Fox(j,L)
						{
								if (i<K)
									P[k++].x=A;
								else
									P[k++].y=A;
							A=((LL)X*A+Y)%Z+1;
						}
				}
			// sort deposits by position
			sort(P,P+N);
			// init segment tree
				for(sz=1;sz<N+1;sz<<=1);
			Fill(treeD,60);
			Fill(treeS,60);
			Fill(lazyM,0);
			// DP
				while (!MD.empty())
					MD.pop();
			MD.push(-1);
			dyn[0]=0;
			UpdateD(1,0,sz-1,0,0);
			j=0;
				Fox(i,N)
				{
					// update tree back to index of previous larger depth
						while ((MD.size()>1) && (P[MD.top()].y<=P[i].y))
							MD.pop();
					UpdateM(1,0,sz-1,MD.top()+1,i,P[i].y);
					MD.push(i);
					// advance left marker while it's too far away
						while (P[j].x<P[i].x-2*M)
							j++;
					// query optimal DP value
					d=S+QueryS(1,0,sz-1,j,i);
					dyn[i+1]=d;
					// insert DP value into tree
					UpdateD(1,0,sz-1,i+1,d);
				}
			// output
			printf("Case #%d: %lld\n",t,dyn[N]);
		}
	return(0);
}