Problem: hire_flyers (2021 finals)

The market is hot for geological talent! Hiring agents are competing to display their job flyers on street intersections across \(T\) towns.

A town's streets can be represented as an infinite 2D grid with rows numbered by increasing integers from North to South and columns numbered by increasing integers from West to East.

There are \(N\) hiring agents, numbered from \(1\) to \(N\). Agent \(i\) starts at the intersection of row \(R_i\) and column \(C_i\), holding \(P_i\) flyers, and facing the cardinal direction \(D_i\) (`"N"` for North, `"S"` for South, `"E"` for East, or `"W"` for West). Each *turn* taken by an agent consists of the following:

  1. Post one of their own flyers at their current intersection, shredding any competing flyer that may have previously been there.
  2. If the agent has more flyers, move to the adjacent intersection in direction \(D_i\).
  
The agents will take turns posting one flyer at a time. Agent \(1\) will take a turn, followed by agent \(2\), and so on until agent \(N\) takes a turn, at which point agent \(1\) will go again (if necessary). Note that there may be multiple agents occupying the same intersection at any point in time.

Let \(F_i\) be the number of flyers placed by agent \(i\) which remain will unshredded at the end. Your job is to compute the sum of \(i * F_i\) over all agents \(i\). As this sum may be very large, you should only compute it modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 75\)
\(1 \le N \le 800{,}000\)
\(0 \le R_i, C_i \le 1{,}000{,}000{,}000\)
\(1 \le P_i \le 1{,}000{,}000{,}000\)
\(D_i \in \{\)`"N"`, `"S"`, `"E"`, `"W"`\(\}\)

The sum of \(N\) across all towns is at most \(2{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of towns. For each town, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which consists of \(3\) space-separated integers \(R_i\), \(C_i\), and \(P_i\), followed by a space-separated character, \(D_i\).


# Output

For the \(i\)th town, print a line containing *"Case #i: "* followed by a single integer, the sum of \(i * F_i\) over all agents \(i\), modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

In the first town, the relevant portion of the grid will end up with the following flyers (with `"."` representing an intersection with no flyer), yielding an answer of \((1 * 3 + 2 * 2 + 3 * 1 + 4 * 1) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 14\):

{{PHOTO_ID:1597395337265553|WIDTH:180}}

In the second town, the relevant portion of the grid will end up with the following flyers, yielding an answer of \((1 * 2 + 2 * 2 + 3 * 2 + 4 * 2) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 20\):

{{PHOTO_ID:4543454065770744|WIDTH:234}}

In the third town, each of agent \(2\)'s turns will involve shredding the last flyer placed by agent \(1\) and replacing it with her own. This will result in \(1{,}000{,}000{,}000\) intersections containing agent \(2\)'s flyers, for an answer of \((2 * 1{,}000{,}000{,}000) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 999999993\).

In the fourth town, the relevant portion of the grid will end up with the following flyers:

{{PHOTO_ID:451563133198975|WIDTH:360}}


Sample input:
5
4
0 0 4 N
0 0 3 S
0 0 2 W
0 0 1 E
4
1 1 3 E
1 3 3 S
3 3 3 W
3 1 3 N
2
0 0 1000000000 N
0 0 1000000000 N
5
4 4 4 W
3 5 3 W
3 3 3 S
3 3 3 E
5 5 5 N
15
7 2 8 N
5 9 7 W
4 6 5 E
1 10 9 W
8 6 3 S
5 6 5 E
10 6 4 N
8 6 6 W
10 2 3 N
7 7 3 S
3 5 9 S
5 1 4 E
9 1 8 E
6 10 1 N
5 9 5 S


Sample output:
Case #1: 14
Case #2: 20
Case #3: 999999993
Case #4: 40
Case #5: 431


Solution: Each contiguous portion of a hiring agent's path can be represented as a 2D segment with \(6\) properties (agent's index, segment's initial row, segment's initial column, turns taken by the agent before reaching the segment's initial row/column, direction, and segment length). Each agent's full path corresponds to one such segment (with \(0\) turns taken before reaching it), but we may want to split/trim/remove some of these segments, based on which portions of them "cover" portions of others (visit cells later, thus replacing their flyers).

For each relevant row containing \(a_1\) `'E'` agents and \(a_2\) `'W'` agents (with \(a_1 + a_2 \gt 0\)), our first goal will be to transform all of its `'E'` agents' segments into a disjoint set of segments. For these, if segment \(s_1\) begins in an earlier column than segment \(s_2\) (or also in the same column if \(s_1\)'s agent index is greater than \(s_2\)'s), then \(s_1\) will cover \(s_2\) up to the end of \(s_1\), meaning that \(s_2\) should be trimmed to begin past that column (or removed entirely if it would become empty). Based on this idea, the `'E'` agents can be handled in \(O(a_1 \log(a_1))\) time, involving sorting them by their initial columns. We can repeat much the same process to transform all of the `'W'` agents' segments into a disjoint set of segments.

Our next step will be to combine the `'E'` and `'W'` segments together into a single disjoint set of segments. This can be done in \(O((a_1 + a_2)\log(a_1 + a_2))\) time using a line sweep across the segments' endpoints. For each interval between such endpoints, if it has at most ongoing segment (either `'E'` or a `'W'`), we'll simply keep that segment (trimmed down to that interval). On the other hand, if the interval has both a `'E'` and a `'W'` segment ongoing, we can compute how they interact within that interval, with the `'E'` segment potentially covering some right portion of the `'W'` segment and vice versa (resulting in at most disjoint \(2\) segments for the interval). Note that we'll end up with \(O(a_1 + a_2)\) segments overall.

Finally, all of the above should be repeated for each relevant column, transforming all of the `'S'` and `'N'` agents' segments into a disjoint set of segments. Based on the \(O(N)\) transformed segments, we can then trivially compute a base answer, ignoring interactions of horizontal segments with vertical ones.

What remains is subtracting from the answer based on each cell at which a horizontal segment intersects with a vertical one, with one segment covering the other there. We'll consider each possible pair of directions (`'E'` covered by `'S'`, `'N'` covered by `'W'`, etc.) independently. Through a combination of \(90 \degree\) rotations and axis-aligned flips of the entire grid and its segments, all \(8\) direction pairs can be transformed into just considering `'E'` covered by `'S'`.

We'll perform a line sweep downward through the `'E'` segments' rows and the `'S'` segments top/bottom rows, while maintaining some info about the ongoing `'S'` segments. It's possible to compute a constant "time value" for each `'E'`/`'S'` segment such that, whenever \(2\) segments intersect, the one with the larger time value will cover the other. In particular, a way to compute this time value (properly accounting for row/column offsets and breaking ties based on agent indices) is \(N*(\)(turns previously taken by agent) \(-\) (initial row) \(-\) (initial column)\() + \) (agent index).

We can therefore maintain a 2D segment tree (over the \(O(N)\) coordinate-compressed relevant columns), with each node of the tree storing the set of time values of ongoing `'S'` segments in its interval of columns (most conveniently in an order statistics tree, though a coordinate-compressed Fenwick tree can also work). Whenever a `'S'` segment starts or ends, we'll update the segment tree accordingly, and whenever an `'E'` segment is encountered, we can compute the number of its cells which are covered by querying for the number of time values greater than its own time value present in its interval of columns.

The total time complexity of this solution is \(O(N \log^2(N))\), due to updating and querying the 2D segment tree \(O(N)\) times.


Code: #include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int N;

struct Seg {  // Directions: U / R / D / L
  int i = -1, r, c, p, d, t = 0;

  long long get_time_val() {
    return N * ((long long)t - r - c) + i;
  }

  bool operator<(const Seg& b) const {
    return make_pair(r, c) < make_pair(b.r, b.c);
  }
};

struct BIT {
  int N;
  vector<int> V;

  BIT() {}

  BIT(int _N): N(_N) {
    init(_N);
  }

  void init(int _N) {
    N = _N;
    V.resize(N + 1);
  }

  void clear() {
    fill(V.begin(), V.end(), 0);
  }

  void update(int i, int v) {
    for (i++; i <= N; i += (i & -i)) {
      V[i] += v;
    }
  }

  int query(int i) {
    int v = 0;
    i = min(i, N - 1);
    for (i++; i > 0; i -= (i & -i)) {
      v += V[i];
    }
    return v;
  }
};

struct SegTree {
  int N, sz;
  vector<vector<long long>> keys;
  vector<BIT> B;

  SegTree() {}

  SegTree(int _N) {
    init(_N);
  }

  void init(int _N) {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1)
      ;
    keys.resize(sz << 1);
    B.resize(sz << 1);
  }

  void init_keys() {
    for (int i = sz; i < sz + N; i++) {
      auto &K = keys[i];
      sort(K.begin(), K.end());
      B[i].init(K.size());
    }
    for (int i = sz - 1; i >= 1; i--) {
      auto &K = keys[i];
      auto &c1 = keys[i << 1], &c2 = keys[(i << 1) + 1];
      int a = 0, b = 0;
      while (a < c1.size() || b < c2.size()) {
        if (b == c2.size() || (a < c1.size() && c1[a] < c2[b])) {
          K.push_back(c1[a++]);
        } else {
          K.push_back(c2[b++]);
        }
      }
      B[i].init(K.size());
    }
  }

  int query_larger(int a, int b, long long v, int i = 1, int r1 = 0, int r2 = -1) {
    if (r2 < 0) {
      a = max(a, 0);
      b = min(b, sz - 1);
      if (a > b) {
        return 0;
      }
      r2 = sz - 1;
    }
    if (a <= r1 && r2 <= b) {
      auto &K = keys[i];
      v = lower_bound(K.begin(), K.end(), v) - K.begin();
      return B[i].query(K.size() - 1) - B[i].query(v - 1);
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    int res = 0;
    if (a <= m) {
      res += query_larger(a, b, v, c, r1, m);
    }
    if (b > m) {
      res += query_larger(a, b, v, c + 1, m + 1, r2);
    }
    return res;
  }

  void update_one(int i, long long v, int d) {
    i += sz;
    while (i >= 1) {
      auto &K = keys[i];
      B[i].update(lower_bound(K.begin(), K.end(), v) - K.begin(), d);
      i >>= 1;
    }
  }
};

vector<Seg> SS;

Seg trim_seg(Seg s, int a, int b, bool hor) {
  if (s.d == 1 || s.d == 2) {    // Forward segment.
    int& sv1 = hor ? s.c : s.r;  // First value.
    int sv2 = sv1 + s.p - 1;     // Last value.
    int t1 = max(0, a - sv1);    // Truncation at start.
    int t2 = max(0, sv2 - b);    // Truncation at end.
    sv1 += t1, s.t += t1;
    s.p -= t1 + t2;
  } else {                       // Backward segment.
    int& sv2 = hor ? s.c : s.r;  // Last value.
    int sv1 = sv2 - (s.p - 1);   // First value.
    int t1 = max(0, a - sv1);    // Truncation at start.
    int t2 = max(0, sv2 - b);    // Truncation at end.
    sv2 -= t2, s.t += t2;
    s.p -= t1 + t2;
  }
  return s;
}

vector<Seg> merge_opp_segs(Seg s1, Seg s2, bool hor) {
  int nc = (hor ? s2.c - s1.c : s2.r - s1.r) + 1;
  int t1 = s1.t;                                  // Time for s1 to reach start.
  int t2 = s2.t + nc - 1 - (s2.i < s1.i ? 1 : 0); // Time for s2 to reach start.
  int m = (hor ? s1.c : s1.r) + (t2 - t1 + 2) / 2 -
            1; // Last value painted over by s2.
  vector<Seg> S;
  S.push_back(trim_seg(s2, -1e9 - 1, m, hor));
  S.push_back(trim_seg(s1, m + 1, 2e9 + 1, hor));
  return S;
}

void process_linear_segs(vector<Seg> V, bool hor) {
  // Collect and sort forward / backward segments.
  int d1, d2;
  if (hor) {
    d1 = 1;
    d2 = 3;
  } else {
    d1 = 2;
    d2 = 0;
  }
  vector<tuple<int, int, Seg>> P1, P2;
  for (auto s : V) {
    if (s.d == d1) {
      P1.emplace_back(s.r + s.c, -s.i, s);
    } else {
      P2.emplace_back(-(s.r + s.c), -s.i, s);
    }
  }
  sort(P1.begin(), P1.end());
  sort(P2.begin(), P2.end());
  // Reduce forward / backward segments independently.
  vector<Seg> S1, S2;
  int last = -1e9 - 1;
  for (auto p : P1) {
    Seg s = trim_seg(get<2>(p), last + 1, 2e9 + 1, hor); // Trim to after last.
    if (s.p > 0) {                                   // Include if not obsolete.
      S1.push_back(s);
    }
    last = max(last, (hor ? s.c : s.r) + (s.p - 1));
  }
  last = 2e9 + 1;
  for (auto p : P2) {
    Seg s = trim_seg(get<2>(p), -1e9 - 1, last - 1, hor); // Trim to before last.
    if (s.p > 0) {                                    // Include if not obsolete.
      S2.push_back(s);
    }
    last = min(last, (hor ? s.c : s.r) - (s.p - 1));
  }
  // Merge forward / backward segments.
  vector<tuple<int, int, int>> E;
  for (int i = 0; i < S1.size(); i++) {
    Seg s = S1[i];
    int sv = hor ? s.c : s.r;
    E.emplace_back(sv, 1, i);
    E.emplace_back(sv + s.p, 0, i);
  }
  for (int i = 0; i < S2.size(); i++) {
    Seg s = S2[i];
    int sv = hor ? s.c : s.r;
    E.emplace_back(sv - (s.p - 1), 3, i);
    E.emplace_back(sv + 1, 2, i);
  }
  sort(E.begin(), E.end());
  vector<int> inds{-1, -1};
  for (int i = 0; i < E.size(); i++) {
    int v = get<0>(E[i]), e = get<1>(E[i]);
    // Update set of ongoing segments.
    int j = e / 2;
    if (e % 2) {
      inds[j] = get<2>(E[i]);
    } else {
      inds[j] = -1;
    }
    // Process ongoing segments?
    if (i + 1 < E.size() && v < get<0>(E[i + 1])) {
      vector<Seg> S;
      if (inds[0] >= 0 && inds[1] >= 0) {
        S = merge_opp_segs(S1[inds[0]], S2[inds[1]], hor);
      } else if (inds[0] >= 0) {
        S.push_back(S1[inds[0]]);
      } else if (inds[1] >= 0) {
        S.push_back(S2[inds[1]]);
      }
      for (auto s : S) {
        Seg s2 = trim_seg(s, v, get<0>(E[i + 1]) - 1, hor);
        if (s2.p > 0) {
          SS.push_back(s2);
        }
      }
    }
  }
}

int solve() {
  SS.clear();
  map<int, vector<Seg>> rowS, colS;
  // Input.
  cin >> N;
  for (int i = 0; i < N; i++) {
    Seg s;
    s.i = i + 1;
    char d;
    cin >> s.r >> s.c >> s.p >> d;
    s.d = d == 'N' ? 0 : d == 'E' ? 1 : d == 'S' ? 2 : 3;
    if (s.d % 2) {
      rowS[s.r].push_back(s);
    } else {
      colS[s.c].push_back(s);
    }
  }
  // Reduce each relevant row / column to disjoint segments
  for (auto p : rowS) {
    process_linear_segs(p.second, true);
  }
  for (auto p : colS) {
    process_linear_segs(p.second, false);
  }
  // Compute base answer.
  int ans = 0;
  for (auto s : SS) {
    ans = (ans + (long long)s.i * s.p) % MOD;
  }
  // Consider 4 different rotations of the grid.
  for (int r = 0; r < 4; r++) {
    // Rotate everything 90 degrees clockwise.
    for (int i = 0; i < SS.size(); i++) {
      Seg &s = SS[i];
      int r = s.r, c = s.c, d = s.d;
      s.r = c;
      s.c = -r;
      s.d = (d + 1) % 4;
    }
    // Consider 2 different vertical flips of the grid.
    for (int _ : {0, 1}) {
      // Flip everything vertically.
      for (int i = 0; i < SS.size(); i++) {
        Seg &s = SS[i];
        s.r = -s.r;
        if (s.d % 2 == 0) {
          s.d = 2 - s.d;
        }
      }
      // Assemble list of line sweep events and distinct D segment columns.
      vector<tuple<int, int, Seg>> E;
      vector<int> cc;
      for (auto s : SS) {
        if (s.d == 1) {  // R
          E.emplace_back(s.r, 1, s);
        } else if (s.d == 2) {  // D
          E.emplace_back(s.r, 0, s);
          E.emplace_back(s.r + s.p - 1, 2, s);
          cc.push_back(s.c);
        }
      }
      sort(E.begin(), E.end());
      sort(cc.begin(), cc.end());
      cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
      // Initialize 2D segment tree.
      SegTree ST(cc.size());
      for (auto s : SS) {
        if (s.d == 2) { // D
          ST.keys[ST.sz + (lower_bound(cc.begin(), cc.end(), s.c) - cc.begin())]
              .push_back(s.get_time_val());
        }
      }
      ST.init_keys();
      // Line sweep to subtract R segments covered by D ones.
      for (auto p : E) {
        int e = get<1>(p);
        Seg s = get<2>(p);
        if (e == 1) {
          int a = lower_bound(cc.begin(), cc.end(), s.c) - cc.begin();
          int b = lower_bound(cc.begin(), cc.end(), s.c + s.p) - cc.begin() - 1;
          long long v = s.get_time_val();
          ans = (ans + MOD - (long long)s.i * ST.query_larger(a, b, v) % MOD) % MOD;
        } else {
          ST.update_one(
            lower_bound(cc.begin(), cc.end(), s.c) - cc.begin(),
            s.get_time_val(),
            e == 0 ? 1 : -1
          );
        }
      }
    }
  }
  return ans;
}

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