Problem: perimetric_ch1 (2020 round1)

**Note: This problem shares similarities with Chapters [2](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A2) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A3). The solution to any chapter may help with solving the others, so please consider reading all of them.**

After a highly successful haul from the log drive, Connie the contractor is tasked with building a number of houses in the Great White North. For each job, the client has provided a floor plan consisting of \(N\) rectangular rooms, numbered from 1 to \(N\). From a bird's-eye view, the rooms are arranged on a 2-dimensional plane, with axis-aligned walls. The southern wall of each room has y-coordinate 0.

The \(i\)th rectangular room has southwest corner \((L_i, 0)\) and northeast corner \((L_i + W, H_i)\). **In this chapter of the problem, all \(N\) rooms have the same width \(W\), and have strictly increasing \(L\) values \((L_1 < L_2 < ... < L_N)\).** Since houses often have shared regions (such as a common living/dining area), these rooms may overlap with one another.

Unfortunately, [log houses are quite susceptible to air leakage](https://www.energy.gov/energysaver/types-homes/energy-efficiency-log-homes). Connie knows that she must install additional insulation to keep the houses warm and energy-efficient during the harsh Canadian winters. In order to determine the amount of insulation material required, Connie will first need to gather some metrics: the perimeters around various combinations of rooms.

Specifically, let \(P_i\) be the perimeter of the union of rooms \(1..i\). Note that any given point is considered to be within the union if and only if it's within at least one of the rooms' rectangles (including right on an edge), and that the union might not form a single connected polygon. Please help compute the product \((P_1 * P_2 * ... * P_N)\). As this product may be very large, you should compute its value modulo 1,000,000,007.

In order to reduce the size of the input, the rooms' coordinates will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(L_{1..K}\) and \(H_{1..K}\), as well as the two quadruples of constants \((A_L, B_L, C_L, D_L)\) and \((A_H, B_H, C_H, D_H)\), and must then compute \(L_{(K+1)..N}\) and \(H_{(K+1)..N}\) as follows:

\(L_i = ((A_L * L_{i-2} + B_L * L_{i-1} + C_L) \text{ modulo } D_L) + 1\) for \(i > K\)
\(H_i = ((A_H * H_{i-2} + B_H * H_{i-1} + C_H) \text{ modulo } D_H) + 1\) for \(i > K\)

# Input

Input begins with an integer \(T\), the number of floor plans. For each plan, there are 5 lines. 

The first line contains the 3 space-separated integers \(N\), \(K\), and \(W\).

The second line contains the \(K\) space-separated integers \(L_{1..K}\).

The third line contains the 4 space-separated integers \(A_L\), \(B_L\), \(C_L\), and \(D_L\).

The fourth line contains the \(K\) space-separated integers \(H_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_H\), \(B_H\), \(C_H\), and \(D_H\).

# Output

For the \(i\)th floor plan, print a line containing *"Case #i: "* followed by a single integer, the product \((P_1 * P_2 * ... * P_N)\) as defined above, modulo 1,000,000,007.

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 1,000,000\)
\(2 \le K \le N\)
\(1 \le W \le 20\)
\(0 \le A_L, B_L, C_L, A_H, B_H, C_H \le 1,000,000,000\)
\(1 \le D_L, D_H \le 500,000,000\)
\(1 \le L_i \le D_L\)
\(1 \le H_i \le D_H\)
\(L_1 < L_2 < ... < L_N\)

The sum of \(N\) across all floor plans is at most 10,000,000.

# Explanation of Sample

For the first floor plan, \(L = [1, 2]\) and \(H = [3, 3]\). The union of just the first room's rectangle is equivalent to that rectangle, which has a width of 2 and a height of 3, and therefore a perimeter of 10. The union of both rooms' rectangles is equivalent to a single rectangle with a width of 3 and a height of 3 (with southwest corner (1, 0)), having a perimeter of 12. The answer is therefore \((10 * 12)\text{ modulo }1\text{,}000\text{,}000\text{,}007 = 120\).

For the second floor plan, \(P = [10, 20]\).

For the third floor plan, \(P = [14, 18, 24, 36, 42]\).

For the fourth floor plan: 
\(L = [9, 14, 15, 19, 23, 27, 31, 35, 39, 43]\)
\(H = [12, 7, 16, 31, 30, 27, 16, 17, 2, 15]\)
\(P = [40, 50, 60, 98, 106, 114, 122, 130, 138, 146]\)


Sample input:
5
2 2 2
1 2
0 0 0 100
3 3
0 0 0 100
2 2 2
10 20
0 0 0 100
3 3
0 0 0 100
5 5 3
2 4 5 9 12
0 0 0 100
4 3 6 3 2
0 0 0 100
10 3 8
9 14 15
0 1 3 53
12 7 16
5 2 1 38
50 10 17
4 9 10 26 28 59 97 100 105 106
1 0 7 832
130 12 82 487 12 30 214 104 104 527
21 81 410 605


Sample output:
Case #1: 120
Case #2: 200
Case #3: 9144576
Case #4: 803986060
Case #5: 271473330


Solution: We'll process the rectangles one by one while computing \(P_{1..N}\). When processing the \(i\)th rectangle, we can't afford to compute the perimeter of the union of the first \(i\) rectangles from scratch (as this would result in an inefficient algorithm with time complexity at least \(O(N^2)\)), so we'll instead compute how the inclusion of this rectangle affects the existing rectangle union (and therefore how \(P_i\) differs from \(P_{i-1}\), assuming that \(P_0 = 0\)).

If the \(i\)th rectangle does not overlap (inclusively) with any existing rectangles (in other words, if either \(i = 1\) or \(L_i > L_{i-1} + W\)), then its entire perimeter will be added to the union's perimeter: \(P_i = P_{i-1} + 2(W + H_i)\).

Otherwise, let's separately consider the amount of horizontal and vertical perimeter added. The amount of additional horizontal perimeter is simply the amount of extra width that the union's perimeter spans, multiplied by two (to account for both the top and the bottom): \(2(L_i - L_{i-1})\). Meanwhile, the amount of additional vertical perimeter is dependent on the largest height \(h\) of any existing rectangle which the \(i\)th one overlaps (inclusively) with. Specifically, if \(H_i \le h\), then there is no additional vertical perimeter (as the top of the union still only comes down from \(h\) to \(0\)), while there will otherwise be \(2(H_i - h)\) additional vertical perimeter (as the top of the union goes up to a height of \(H_i\) and then back down).

The simplest way to compute \(h\) in the above expression is to loop back over all of the rectangles overlapping with the \(i\)th one, which are at most the last \(W\) ones. This approach results in a time complexity of \(O(NW)\), which is sufficient.

However, it can also be optimized down to just \(O(N)\) by maintaining a deque of rectangles which could possibly be relevant for this purpose in the future (that is, ones whose \(L\) values are no less than \(L_i - W\), and which have both increasing \(L\) values and decreasing \(H\) values). The rectangle with the largest height overlapping with the \(i\)th one is then known to be the earliest one in this deque.


Code: // Perimetric - Chapter 1
// Solution by 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 <unordered_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);

#define GETCHAR getchar_unlocked

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 1000001
#define MOD 1000000007

int W;
LL cur, ans;
int L[LIM], H[LIM];
PR Q[LIM];
int Qs, Qe;

void ReadSeq(int* V, int N, int K)
{
  int i, A, B, C, D;
  Fox(i, K)
    Read(V[i]);
  Read(A), Read(B), Read(C), Read(D);
  FoxI(i, K, N - 1)
    V[i] = ((LL)A * V[i - 2] + (LL)B * V[i - 1] + C) % D + 1;
}

void ProcessRect(int L, int H)
{
  // remove rectangles which are no longer relevant (too far left)
  while (Qe != Qs && Q[Qs].x < L)
    Qs++;
  if (Qe == Qs)
    cur += W + H; // no overlap, so add full rectangle perimeter
  else
  {
    cur += L + W - Q[Qe - 1].x; // add additional horizontal perimeter
    cur += max(0, H - Q[Qs].y); // add additional vertical perimeter
  }
  // remove rectangles which are no longer relevant (shorter than this one)
  while (Qe != Qs && Q[Qe - 1].y <= H)
    Qe--;
  // add this rectangle
  Q[Qe++] = mp(L + W, H);
}

int ProcessCase()
{
  int N, K, i;
  // input
  Read(N), Read(K), Read(W);
  ReadSeq(L, N, K);
  ReadSeq(H, N, K);
  // process rectangles, while maintaining queue of relevant ones
  cur = 0, ans = 1;
  Qs = Qe = 0;
  Fox(i, N)
  {
    ProcessRect(L[i], H[i]);
    ans = ans * (cur % MOD) * 2 % MOD;
  }
  return(ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}