Problem: auth-ore-ization (2021 round3)

Facebulk Inc. is a mining company whose Bulk Geological Processing (BGP) network has been disrupted lately. To ensure that buildings are more accessible in future outages, the company has hired emergency response agents for testing across each of its \(T\) ore-processing plants.

A given plant consists of \(3N\) rooms arranged in a grid of \(N\) rows and \(3\) columns. The room in the \(i\)th row from the top and the \(j\)th column from the left can be referred to as room \((i, j)\). Each room \((i, j)\) has an authorization level of \(A_{i,j}\), meaning that only agents with authorization levels \(A_{i,j}\) or greater may enter it.

\(M\) agents have been tasked to independently navigate the grid. The \(i\)th agent, who has an authorization level of \(L_i\), begins in room \((R1_i, C1_i)\) and would like to reach a different room \((R2_i, C2_i)\). It's guaranteed that they are authorized to be in both of those rooms (that is, \(L_i \ge A_{R1_i,C1_i}\) and \(L_i \ge A_{R2_i,C2_i}\)). The agent may make one or more moves, each consisting of moving to an adjacent room that they're also authorized to enter. Two rooms \((i_1, j_1)\) and \((i_2, j_2)\) are considered to be adjacent if they share a wall (that is, if \(|i_1 - i_2| + |j_1 - j_2| = 1\)).

Let \(D_i\) equal the minimum number of moves required for the \(i\)th agent to travel from room \((R1_i, C1_i)\) to room \((R2_i, C2_i)\), with \(D_i\) considered to equal \(1\) if the \(i\)th agent cannot complete their trip at all.

Please help Facebulk evaluate the emergency accessibility of its buildings by computing the product of \(D_{1..M}\). As this product may be very large, you should compute its value modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 70\)
\(1 \le N, M \le 1{,}000{,}000\)
\(1 \le A_{i,j} \le 10^9\)
\(1 \le R1_i, R2_i \le N\)
\(1 \le C1_i, C2_i \le 3\)
\(1 \le L_i \le 10^9\)

The sum of \(N+M\) across all plants is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of ore-processing plants. For each plant, there is first a line containing \(2\) space-separated integers, \(N\) and \(M\). Then, \(N\) lines follow, the \(i\)th of which contains \(3\) space-separated integers, \(A_{i,1..3}\). Then, \(M\) lines follow, the \(i\)th of which contains \(5\) space-separated integers, \(R1_i\), \(C1_i\), \(R2_i\), \(C2_i\), and \(L_i\).


# Output

For the \(i\)th plant, print a line containing *"Case #i: "* followed by a single integer, the product of \(D_{1..M}\) as defined above, modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

In the first plant, the first agent cannot reach room \((1, 3)\) from room \((1, 1)\) as they're not authorized to enter room \((1, 2)\). On the other hand, the second agent can move into room \((1, 2)\) and then into room \((1, 3)\), taking a total of \(2\) moves. Therefore, \(D = [1 \mathrm{\;(impossible),\,} 2]\), and so the answer is \((1 \cdot 2) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 2\).

In the second plant, the first agent's shortest route is through rooms \((1, 3) \to (1, 2) \to (1, 1)\). Meanwhile, \((1, 3) \to (2, 3) \to (3, 3) \to (3, 2) \to (3, 1) \to (2, 1) \to (1, 1)\) is the second agent's shortest route. Overall, \(D = [2, 6, 3, 1 \mathrm{\;(impossible),\,} 2, 4]\), and so the answer is \((2 \cdot 6 \cdot 3 \cdot 1 \cdot 2 \cdot 4) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 288\).

In the third plant, \(D = [10]\).

In the fourth plant, \(D = [8, 5, 1 \mathrm{\;(impossible),\,} 11, 14, 10, 4, 3, 7, 8, 5, 7, 5, 7, 8]\).


Sample input:
4
1 2
1 2 1
1 1 1 3 1
1 1 1 3 2
3 6
1 5 3
1 9 1
4 2 1
1 3 1 1 8
1 3 1 1 4
1 1 3 2 4
1 1 3 2 3
2 1 2 3 9
2 1 2 3 8
5 1
1 1 1
1 9 9
1 1 1
9 9 1
1 1 1
1 3 5 1 1
10 15
10 5 6
4 2 5
6 9 1
3 7 3
6 9 4
9 1 5
5 10 1
4 2 6
8 9 1
1 2 4
9 3 2 2 9
8 1 6 2 8
2 2 10 1 5
10 1 2 2 8
5 1 7 1 6
10 3 1 2 7
4 1 6 3 7
9 3 8 1 10
3 3 9 2 9
10 3 4 1 7
7 1 6 3 6
8 2 2 3 10
10 2 8 1 7
1 1 7 2 10
1 3 9 3 9


Sample output:
Case #1: 2
Case #2: 288
Case #3: 10
Case #4: 672957165


Solution: We'll process the agents in increasing order of authorization level, computing the \(D\) value for each one in turn. Let \(G_{i,j} = 1\) if agents with the current authorization level may enter room \((i, j)\), which is the only information required to process an agent. All \(G\) values are initially \(0\), and before processing each next agent with an authorization level of \(x\), we'll consider each room \((i, j)\) such that \(A_{i,j}\) is greater than the previous agent's authorization level and no greater than \(x\), and set \(G_{i,j}\) to \(1\) for each one. Overall, this process boils down to processing a list of \(3N + M\) events sorted by authorization level.

When processing agent \(i\), assuming \(R1_i \le R2_i\) w.l.o.g., we can consider any potentially optimal route to consist of the following sequence of segments:

  1. Move from room \((R1_i, C1_i)\) to some room \((R1_i, a)\) in the initial row such that \(G_{R1_i,a} = 1\).
    a) If \(a = C1_i\), this requires \(0\) moves.
    b) If \(|C1_i - a| = 1\), this requires \(1\) horizontal move.
    c) Otherwise, if \(|C1_i - a| = 2\), this can be done by first moving up to cell \((x, C1_i)\) (in some row \(x\) such that \(x \le R1_i\)), then across to cell \((x, a)\), and finally back down to cell \((R1_i, a)\), assuming all involved cells have \(G\) values of \(1\). This requires \(2(R1_i - x) + 2\) moves, though there might be no valid choice of \(x\). If any valid rows \(x\) do exist, the best one will be the largest \(x\) such that \(x \le R1_i\) and \(G_{x,2} = 1\).
  2. Move from room \((R1_i, a)\) down to some room \((R2_i, b)\) in the final row such that \(G_{R2_i,b} = 1\), using only downward and horizontal moves (upward moves would be of no use).
  3. Move from room \((R2_i, b)\) to the final room \((R2_i, C2_i)\). This segment is nearly identical to segment #1, just mirrored vertically — for example, if \(|C2_i - b| = 2\), this can be done by moving down to some row \(y\) such that \(y \ge R2_i\).

For each agent \(i\), we'll consider all \(9\) possible combinations of \(a\) and \(b\), and evaluate the number of moves involved in the route dictated by each (if a valid path exists).

For segment #1, only the \(|C1_i - a| = 2\) case is tricky. To handle it, we should start by computing the best candidate value of \(x\), which can be done in \(O(\log(N))\) time if we maintain an ordered set of row indices \(j\) such that \(G_{j,2} = 1\) (which we can in a total of \(O(N\log(N))\) time). To determine whether \(x\) is valid, we can compare it against the largest row \(x'\) such that \(x' \le R1_i\) and \(G_{x',0} = 0\) or \(G_{x',2} = 0\). A set of such rows \(x'\) can similarly be maintained in a total of \(O(N \log(N))\) time and queried in \(O(\log(N))\) time per route. Finally, a near-identical process may be repeated for segment #3.

To help with segment #2, we'll maintain a segment tree over the \(N\) rows. Each node \(i\) representing an interval of rows \(x_i..y_i\) will store a \(3 \times 3\) matrix \(M_i\) such that \(M_{i,a,b}\) is the minimum number of moves currently required to move from room \((x_i, a)\) to room \((y_i, b)\) using only downward and horizontal moves.

The matrices from two adjacent intervals' nodes \(i\) and \(j\) (such that \(y_i + 1 = x_j)\) can be combined to obtain a matrix \(M'\) for rows \(x_i..y_j\) by considering each possible transitionary column \(c\) for moving from row \(y_i\) to row \(x_j\) — in particular, \(\displaystyle M'_{a,b} = \min_{c=1..3} \{{M_i}_{a,c} + 1 + {M_j}_{c,b}\}\). This can be applied when recomputing a node's matrix based on those of its children (during segment tree updates), and when combining multiple nodes' matrices (during segment tree queries). A matrix computed from querying the segment tree provides exactly the information required to evaluate segment #2 of a route.

Setting each \(G\) value to \(1\) corresponds to a segment tree update, while processing each agent \(i\) requires querying the segment tree for the interval of rows \(R1_i..R2_i\) (assuming \(R1_i \le R2_i)\), each of which can be done in \(O(\log(N))\) time (with a factor of \(3^3\) for dealing with the matrices). This brings up the total time complexity to \(O((N + M)\log(N))\).

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/5sNUbjuRlBA)


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

const int T_INF = 0x3f3f3f3f;
const int INF = T_INF - 1;
const int LIM = 1000000;
const int LIM2 = 2100000;
const int MOD = 1000000007;

struct Event {
  int v, t, r1, c1, r2, c2;
  Event(int v, int r, int c) : v(v), t(0), r1(r), c1(c) {}
  Event(int v, int r1, int c1, int r2, int c2)
      : v(v), t(1), r1(r1), c1(c1), r2(r2), c2(c2) {}
  bool operator<(const Event& o) const {
    return make_pair(v, t) < make_pair(o.v, o.t);
  }
};

int N, M;
vector<Event> E;
bool G[LIM][3];
set<int> G0[3], G1[3];

// tree[r1, r2][a, b] = distance from (r1, a) to (r2, b), going only right.
int sz, tree[LIM2][3][3];
int mk, memK[LIM2][3][3];
long long mem[LIM2][3][3];

long long query(int i, int ir1, int ir2, int r1, int r2, int a, int b) {
  if (r1 == ir1 && ir2 == r2) {  // Full node?
    return tree[i][a][b];
  }
  long long& mm = mem[i][a][b];
  if (memK[i][a][b] == mk) {  // Already memoized?
    return mm;
  }
  memK[i][a][b] = mk;
  i <<= 1;
  int m = (ir1 + ir2) >> 1;
  if (r2 <= m) {  // All on left?
    return mm = query(i, ir1, m, r1, r2, a, b);
  }
  if (r1 > m) {  // All on right?
    return mm = query(i + 1, m + 1, ir2, r1, r2, a, b);
  }
  // Consider all possible intermediate columns.
  long long ans = INF;
  for (int c = 0; c < 3; c++) {
    ans = min(
      ans,
      query(i, ir1, m, r1, m, a, c) + 1 + query(i + 1, m + 1, ir2, m + 1, r2, c, b)
    );
  }
  return mm = ans;
}

long long query_path(int r1, int c1, int r2, int c2) {
  long long ans = INF;
  // Consider all possible intermediate column pairs (a, b).
  mk++;
  for (int a = 0; a < 3; a++) {
    for (int b = 0; b < 3; b++) {
      int d1 = tree[sz + r1][c1][a], d2 = tree[sz + r2][c2][b];
      if (d1 > INF && abs(a - c1) == 2 && G[r1][c1] && G[r1][a]) {
        int i = *prev(G1[1].lower_bound(r1));
        if (
          i >= 0 &&
          i > *prev(G0[0].lower_bound(r1)) &&
          i > *prev(G0[2].lower_bound(r1))
        ) {
          d1 = (r1 - i + 1) * 2;
        }
      }
      if (d2 > INF && abs(b - c2) == 2 && G[r2][c2] && G[r2][b]) {
        int i = *G1[1].lower_bound(r2);
        if (
          i < N &&
          i < *G0[0].lower_bound(r2) &&
          i < *G0[2].lower_bound(r2)
        ) {
          d2 = (i - r2 + 1) * 2;
        }
      }
      ans = min(ans, d1 + query(1, 0, sz - 1, r1, r2, a, b) + d2);
    }
  }
  return ans == INF ? 1 : ans;
}

void add_cell(int r, int c) {
  G[r][c] = 1;
  G0[c].erase(r);
  G1[c].insert(r);
  // Update affected leaf node in segment tree.
  int i = sz + r;
  for (int a = 0; a < 3; a++) {
    for (int b = a; b < 3; b++) {
      if (!G[r][b]) {
        break;
      }
      tree[i][a][b] = tree[i][b][a] = b - a;
    }
  }
  // Update ancestors in segment tree.
  while (i > 1) {
    i >>= 1;
    for (int a = 0; a < 3; a++) {
      for (int b = 0; b < 3; b++) {
        for (int c = 0; c < 3; c++) {
          tree[i][a][b] = min(
            tree[i][a][b],
            tree[i << 1][a][c] + 1 + tree[(i << 1) + 1][c][b]
          );
        }
      }
    }
  }
}

int solve() {
  E.clear();
  for (int c = 0; c < 3; c++) {
    G0[c].clear();
    G1[c].clear();
  }
  // Input.
  cin >> N >> M;
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < 3; c++) {
      int a;
      cin >> a;
      E.push_back(Event(a, r, c));
      G0[c].insert(r);
    }
  }
  for (int i = 0; i < M; i++) {
    int r1, c1, r2, c2, l;
    cin >> r1 >> c1 >> r2 >> c2 >> l;
    if (r1 > r2) {
      swap(r1, r2);
      swap(c1, c2);
    }
    E.push_back(Event(l, r1 - 1, c1 - 1, r2 - 1, c2 - 1));
  }
  // Init grid / segment tree.
  memset(G, 0, sizeof(G[0]) * N);
  for (int c = 0; c < 3; c++) {
    G0[c].insert(-1);
    G1[c].insert(-1);
    G0[c].insert(N);
    G1[c].insert(N);
  }
  for (sz = 1; sz < N; sz <<= 1);
  memset(tree, T_INF, sizeof(tree[0]) * sz * 2);
  // Process events.
  int ans = 1;
  sort(E.begin(), E.end());
  for (auto e : E) {
    if (!e.t) {
      add_cell(e.r1, e.c1);
    } else {
      ans = ans * query_path(e.r1, e.c1, e.r2, e.c2) % MOD;
    }
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}