Problem: seafood (2019 round2)

Percy is a harlequin tuskfish who lives on a stretch of the sea floor, which
may be represented as a number line. There are **N** objects resting on the
sand beneath the waves, the _i_th of which is at a positive integral position
**Pi**, is either a clam (if **Oi** = "C") or otherwise a rock (if **Oi** =
"R"), and in either case has a hardness of **Hi**. No two objects are at the
same position, and at least one of the objects is a clam.

Percy initially finds himself at position 0, and can then swim in either
direction along the number line at a rate of 1 unit per second. Whenever he
occupies the same position as a clam, he may pick it up and begin carrying it
around in his mouth. Picking up a clam requires no additional time, and Percy
is talented enough to carry any number of clams at once.

Percy would like to devour the delicious interior of each clam, but can't get
to it without first somehow breaking open its hard shell. Fortunately, Percy
is clever and persistent enough to have a
[solution](https://www.radiotimes.com/news/2018-01-26/blue-planet-2-fish-
clams-tools/) to this problem. Whenever he occupies the same position as a
rock, he may take each clam that he's currently carrying that has a strictly
smaller hardness than that of the rock, knock the clam against the rock to
break open its shell, and eat the meal packaged within! This process requires
no additional time per clam.

What's the minimum amount of time required for Percy to swim around and eat
all of the clams (by picking each one up and then knocking it against a harder
rock than itself), if at all possible?

In order to reduce the size of the input, the object's positions and
hardnesses will not all be provided explicitly. Instead, you'll be given
**P1**, **P2**, **H1**, **H2**, as well as the 8 constants **Ap**, **Bp**,
**Cp**, **Dp**, **Ah**, **Bh**, **Ch**, and **Dh**, and must then compute
**P3..N** and **H3..N** as follows (bearing in mind that intermediate values
may not fit within 32-bit integers):

**Pi** = ((**Ap** * **Pi-2** \+ **Bp** * **Pi-1** \+ **Cp**) modulo **Dp**) + 1, for _i_ = 3 to **N**. 

**Hi** = ((**Ah** * **Hi-2** \+ **Bh** * **Hi-1** \+ **Ch**) modulo **Dh**) + 1, for _i_ = 3 to **N**. 

### Input

Input begins with an integer **T**, the number of days Percy goes hunting for
clams. For each day, there are four lines. The first line contains the integer
**N**. The second line contains the space-separated integers **P1**, **P2**,
**Ap**, **Bp**, **Cp**, and **Dp**. The third line contains the space-
separated integers **H1**, **H2**, **Ah**, **Bh**, **Ch**, and **Dh**. The
fourth line contains the length-**N** string **O1..N**.

### Output

For the _i_th day, print a line containing "Case #_i_: " followed by one
integer, either the minimum number of seconds required for Percy to break open
and eat all of the clams, or -1 if he cannot do so.

### Constraints

1 ≤ **T** ≤ 250  
2 ≤ **N** ≤ 800,000  
0 ≤ **Ap**, **Bp**, **Cp**, **Ah**, **Bh**, **Ch** ≤ 1,000,000,000  
1 ≤ **Dp**, **Dh** ≤ 1,000,000,000  
1 ≤ **Pi** ≤ **Dp**  
1 ≤ **Hi** ≤ **Dh**  

### Explanation of Sample

In the first case, P = [5, 10] and H = [30, 31]. Percy should swim to position
5, pick up the clam with hardness 30, swim onwards to position 10, and break
open the clam on the rock with hardness 31.

In the second case, P = [5, 10] and H = [31, 30]. Percy should now swim to
position 10 to pick up the clam, and then back to position 5 to break it open.

In the third case, P = [5, 10] and H = [30, 30]. Once Percy picks up the clam,
no rock harder than it exists on the sea floor, meaning that he can never
break it open.

In the fourth case, P = [10, 50, 11, 52] and H = [50, 10, 49, 8].

In the fifth case, P = [415, 711, 225, 136, 256, 469, 714, 399, 841, 697, 480,
147, 98, 837, 745, 660, 44, 226, 73, 7] and H = [9, 2, 10, 6, 6, 2, 7, 13, 4,
5, 11, 11, 4, 3, 7, 1, 6, 10, 10, 1].



Sample input:
6
2
5 10 0 0 0 50
30 31 0 0 0 50
CR
2
5 10 0 0 0 50
31 30 0 0 0 50
RC
2
5 10 0 0 0 50
30 30 0 0 0 50
RC
4
10 50 0 1 40 80
50 10 0 1 38 80
RRCC
20
415 711 3 4 3 967
9 2 1 2 9 13
CCCCCRRRCRCCCRRCRRCC
100
168981242 670860915 208968638 604295408 490937286 715757945
627165633 146096256 952913201 456337362 978266551 970054933
CRCCRRRRRRRRCRRCCCRCCRRRRCRCRRRRCCCCRCCRRRCRRRCCCCCRCCRCRCCCCCRRCCCRRCRRRRCCCRCRRCRRRRCCCRRCRCCCCCRR


Sample output:
Case #1: 10
Case #2: 15
Case #3: -1
Case #4: 56
Case #5: 1099
Case #6: 890508817



Code: // Seafood
// 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 800001

int N,K;
int G[2][LIM];
char O[LIM];
pair< int, pair<char,int> > P[LIM];
int C[LIM],B[LIM];
int sufCB[LIM],sufCH[LIM];
int ss,nfr;
PR st[LIM],fr[LIM];

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,j,a,b,c,d,p;
	LL ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input, and generate values
			Read(N);
				Fox(i,2)
				{
					Read(G[i][0]),Read(G[i][1]),Read(a),Read(b),Read(c),Read(d);
						FoxI(j,2,N-1)
							G[i][j]=((LL)a*G[i][j-2] + (LL)b*G[i][j-1] + c)%d+1;
				}
			scanf("%s",&O);
				Fox(i,N)
					P[i]=mp(G[0][i],mp(O[i],G[1][i]));
			// sort objects by position
			sort(P,P+N);
			// get list of clams
			K=0;
				Fox(i,N)
					if (P[i].y.x=='C')
						C[K++]=i;
			// get list of useful rocks up to final clam
			ss=0;
				FoxR(i,C[K-1])
					if ((P[i].y.x=='R') && ((!ss) || (P[i].y.y>st[ss-1].x)))
						st[ss++]=mp(P[i].y.y,P[i].x);
			// get clams' backtrack positions
			Fill(B,-1);
				Fox(i,K)
				{
					j=lower_bound(st,st+ss,mp(P[C[i]].y.y+1,0))-st;
						if (j==ss)
							break;
					B[i]=st[j].y;
				}
			// precompute suffix mins/maxes of clams' backtrack positions/hardnesses
			sufCB[K]=INF,sufCH[K]=0;
				FoxR(i,K)
				{
					sufCB[i]=min(sufCB[i+1],B[i]);
					sufCH[i]=max(sufCH[i+1],P[C[i]].y.y);
				}
			// get list of useful rocks past final clam
			nfr=0;
				FoxI(i,C[K-1]+1,N-1)
					if ((!nfr) || (P[i].y.y>fr[nfr-1].x))
						fr[nfr++]=mp(P[i].y.y,P[i].x);
			// DP
			ans=2*INF;
			ss=0;
				Fox(i,K)
				{
					// perform optional transition from an earlier clam
						if (!i)
							d=0;
						else
						{
							p=P[C[i-1]].x;
								while (ss>1)
								{
									a=st[ss-1].y;
									b=min(a,st[ss-2].y);
										if ((LL)st[ss-1].x+2*max(0,p-a)<(LL)st[ss-2].x+2*max(0,p-b))
											break;
									st[ss-2].y=b;
									ss--;
								}
							d=st[ss-1].x+2*max(0,p-st[ss-1].y);
						}
					st[ss++]=mp(d,B[i]);
					// consider concluding with transition to final clam
					p=P[C[K-1]].x;
						if (sufCB[i]>=0)
							Min(ans,(LL)d+max(0,p-sufCB[i]));
					a=lower_bound(fr,fr+nfr,mp(sufCH[i]+1,0))-fr;
						if (a<nfr)
							Min(ans,(LL)d+(fr[a].y-p));
						if (B[i]<0)
							break;
				}
				if (ans==2*INF)
					ans=-1;
				else
					ans+=P[C[K-1]].x;
			// output
			printf("Case #%d: %lld\n",t,ans);
		}
	return(0);
}