Problem: perimetric_ch2 (2020 round1)

**Note: This problem shares similarities with Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A1) 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_i, H_i\)). **In this chapter of the problem, the rooms have non-increasing \(H\) values \((H_1 \ge H_2 \ge ... \ge H_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}\), \(W_{1..K}\), and \(H_{1..K}\), as well as the three quadruples of constants \((A_L, B_L, C_L, D_L)\), \((A_W, B_W, C_W, D_W)\), and \((A_H, B_H, C_H, D_H)\), and must then compute \(L_{(K+1)..N}\), \(W_{(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\)
\(W_i = ((A_W * W_{i-2} + B_W * W_{i-1} + C_W) \text{ modulo } D_W) + 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 7 lines. 

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

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 \(W_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_W\), \(B_W\), \(C_W\), and \(D_W\).

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

The seventh 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 95\) 
\(2 \le N \le 1,000,000\)
\(2 \le K \le N\)
\(0 \le A_L, B_L, C_L, A_W, B_W, C_W, A_H, B_H, C_H \le 1,000,000,000\)
\(1 \le D_L, D_W, D_H \le 500,000,000\)
\(1 \le L_i \le D_L\)
\(1 \le W_i \le D_W\)
\(1 \le H_i \le D_H\)
\(H_1 \ge H_2 \ge ... \ge H_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 = [24, 38, 46, 58, 70]\).

For the fourth floor plan:
\(L = [14, 5, 14, 27, 13, 14, 12, 2, 18, 43]\) 
\(W = [6, 4, 13, 32, 8, 7, 22, 32, 26, 28]\) 
\(H = [29, 23, 22, 20, 19, 17, 16, 14, 13, 11]\) 
\(P = [70, 124, 138, 202, 204, 204, 206, 190, 190, 214]\)


Sample input:
5
2 2
1 2
0 0 0 100
2 2
0 0 0 100
3 3
0 0 0 100
2 2
10 20
0 0 0 100
2 2
0 0 0 100
3 3
0 0 0 100
5 5
8 3 10 16 2
0 0 0 100
3 1 5 2 18
0 0 0 100
9 6 6 4 1
0 0 0 100
10 3
14 5 14
4 7 2 47
6 4 13
2 3 17 33
29 23 22
1 0 27 31
50 10
100 26 4 28 106 59 9 105 10 97
14 40 784 4832
130 12 82 487 12 30 214 104 104 527
21 81 410 605
938 903 899 899 896 857 841 837 834 834
1 0 924 951


Sample output:
Case #1: 120
Case #2: 200
Case #3: 170325120
Case #4: 81786362
Case #5: 950017190


Solution: As in Chapter 1 of this problem, 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\)).

Because each rectangle is no taller than all existing ones, the exact heights of those existing ones end up not mattering — only their x-coordinates do. As such, we'll maintain an ordered set of non-intersecting intervals of x-coordinates which the rectangle union spans.

Let's separately consider the amount of horizontal and vertical perimeter added for the \(i\)th rectangle. The total horizontal perimeter of the rectangle union is always just the sum of the lengths in the intervals in our set, multiplied by two (to account for both the top and the bottom). Meanwhile, we can observe that the \(i\)th rectangle contributes \(2H_i\) vertical perimeter, minus \(2H_i\) for each existing interval that it overlaps (inclusively) with (as the perimeter is prevented from going all the way down to y-coordinate \(0\) and back up to \(H_i\).

Based on the above observations, as long as we're able to update the ordered set of intervals for each new rectangle (by iterating over ones that it overlaps with, deleting them, and then inserting a new interval spanning the affected x-coordinates), we can also easily update the union's current perimeter along the way. Efficient ordered sets are supported in many programming languages, backed by BBSTs (balanced binary search trees) and capable of supporting the necessary searching, deletion, and insertion operations in logarithmic time in the number of elements in the set. Therefore, given that our ordered set will contain at most \(N\) elements (one interval per rectangle) and that each rectangle's interval will be inserted/deleted at most once, this approach yields a time complexity of \(O(N log(N))\).


Code: // Perimetric - Chapter 2
// 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

LL cur, ans;
int L[LIM], W[LIM], H[LIM];
set<PR> S;

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 R, int H)
{
  // find first x interval overlapping with this rectangle
  auto I = prev(S.lower_bound(mp(L, -1)));
  if (I->y < L)
    I++;
  Min(L, I->x);
  // erase all x intervals overlapping with this rectangle
  while (I->x <= R)
  {
    Max(R, I->y);
    cur -= I->y - I->x + H;
    I = S.erase(I);
  }
  // add x interval for this rectangle (and any intervals it overlapped)
  cur += R - L + H;
  S.insert(mp(L, R));
}

int ProcessCase()
{
  int N, K, i;
  // input
  Read(N), Read(K);
  ReadSeq(L, N, K);
  ReadSeq(W, N, K);
  ReadSeq(H, N, K);
  // process rectangles, while maintaining set of covered x intervals
  cur = 0, ans = 1;
  S.clear();
  S.insert(mp(-1, -1));
  S.insert(mp(INF + 1, INF + 1));
  Fox(i, N)
  {
    ProcessRect(L[i], L[i] + W[i], H[i]);
    ans = (LL)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);
}