Problem: cryptoconference (2020 finals)

Crys just invented a new cryptocurrency and is planning to present it at \(T\) blockchain conferences around the world. The conference schedules are already on their way to being finalized, but Crys is considering how she might get her own talks in at the last minute.

A certain conference is \(K\) hours long, with talks to start and end on the hour. Each talk will span a non-empty inclusive time interval of hours \([x, y]\), such that \(x\) and \(y\) are integers and \(0 \le x \lt y \le K\). \(N\) talks are gradually being added to the schedule, one after another, with the \(i\)th added talk scheduled to span the time interval \([S_i, S_i + D_i]\). The \(N\) talks are not necessarily added in order of starting or ending time. Their time intervals may arbitrarily overlap with one another, and are not necessarily distinct.

Each time a talk is added to the schedule, Crys will then consider submitting a request for her own talk to also be included. This involves proposing a time interval for her talk, which must similarly be an integral interval \([x, y]\) such that \(0 \le x \lt y \le K\). Crys suspects that her request would be rejected if the inclusion of her talk might prevent an attendee from hearing another talk due to her proposed time interval entirely subsuming an already-scheduled one. As such, after the first \(i\) talks have been added to the schedule, she will *not* propose a time interval \([x, y]\) if there exists any existing talk \(j\) \((1 \le j \le i)\) such that \(x \le S_j\) and \(S_j + D_j \le y\).

Letting \(C_i\) be the number of different time intervals which Crys could validly propose for her talk after the first \(i\) talks have been added to the schedule, please determine the value of \((C_1 * C_2 * ... * C_N)\) modulo 1,000,000,007.

# Constraints

\(1 \le T \le 95\)
\(1 \le N \le 300,000\)
\(1 \le K \le 1,000,000,000\)
\(0 \le S_i < K\)
\(1 \le D_i \le K\)
\(1 \le S_i + D_i \le K\)

The sum of \(N\) across all conferences is at most 1,500,000.

# Input

Input begins with an integer \(T\), the number of conferences. For each conference there are \(N + 1\) lines. The first line contains the space-separated integers \(N\) and \(K\). \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(S_i\) and \(D_i\).


# Output

For the \(i\)th conference, print a line containing *"Case #i: "*, followed by a single integer, the product of \(C_{1..N}\) modulo 1,000,000,007.





# Explanation of Sample

In the first conference, once a talk spanning time interval \([1, 2]\) exists, Crys can only propose time intervals \([0, 1]\) and \([2, 3]\) for her talk without subsuming \([1, 2]\). Therefore, \(C = [2]\).

In the second conference, after the first talk (spanning time interval \([1, 3]\)) has been added to the schedule, Crys can propose any of the time intervals \([0, 1]\), \([0, 2]\), \([1, 2]\), or \([2, 3]\). After the introduction of the second talk (spanning time interval \([0, 2]\)), she can only propose \([0, 1]\), \([1, 2]\), or \([2, 3]\). Therefore, \(C = [4, 3]\), and the final answer is (4 * 3) modulo 1,000,000,007 = 12.

In the third conference, \(C = [8, 4]\).

In the fourth conference, \(C = [4126, 3631, 3239, 2687, 2687]\).


Sample input:
6
1 3
1 1
2 3
1 2
0 2
2 4
1 3
2 1
5 100
32 41
14 26
81 12
38 17
68 25
15 321
41 267
235 12
230 72
243 30
319 1
248 40
169 107
10 180
106 117
12 183
291 24
50 153
292 28
87 230
137 23
1 1000000000
0 1000000000


Sample output:
Case #1: 2
Case #2: 12
Case #3: 32
Case #4: 352996146
Case #5: 751550872
Case #6: 20


Solution: We'll maintain a set \(R\) of all "relevant" talk time intervals. An interval \([x, y]\) is considered irrelevant if ignoring it does not change the set of time intervals which may be proposed, which is the case if and only if there exists another interval which is inclusively contained within it (an interval \([x', y']\) such that \(x \le x'\) and \(y' \le y\)).

We'll maintain \(R\) ordered by intervals' start times, in strictly increasing order. Note that this also means that the intervals' end times must be strictly increasing (otherwise, they cannot all be relevant). For convenience, we'll also begin by including dummy intervals \([-1, -1]\) and \([K, K+1]\) in \(R\), whose significance is explained below. From there, updating the set for each new interval may be done relatively straightforwardly in amortized \(O(log(N))\) time, with the new interval either already being irrelevant, or being relevant and causing 0 or more existing intervals to become irrelevant.

What remains is maintaining the corresponding answer for \(R\) — that is, the number of time intervals which may be proposed without subsuming any interval in \(R\). For this purpose, let \(F([x_1, y_1], [x_2, y_2])\) be the number of different intervals \([x_p, y_p]\) which may be proposed such that \(x_1 < x_p \le x_2\), given that \([x_1, y_1]\) and \([x_2, y_2]\) form a pair of consecutive relevant intervals in \(R\). Note that \(F([x_1, y_1], [x_2, y_2])\) does not depend on any intervals in \(R\) besides those two, and may be easily computed in \(O(1)\) time using the fact that the only constraints are \(x_1 < x_p \le x_2\) and \(x_p < y_p < y_2\).

We can observe that the sum of \(F([x_1, y_1], [x_2, y_2])\) over all pairs of consecutive relevant intervals (of which there are \(|R| - 1\)) is equal to the total answer — for example, this is the case when \(R\) consists only of the initial pair of dummy intervals \([-1, -1]\) and \([K, K+1]\), with additional intervals simply partitioning the set of possible start times. We can then maintain this sum with no additional time complexity as we go. For example, when inserting an interval \(X\) between two existing intervals \(A\) and \(B\), we should increase the sum by \(F(A, X) + F(X, B) - F(A, B)\), with deletions handled similarly.

This gives us an algorithm with a time complexity of \(O(N log(N))\).


Code: // Cryptoconference
// 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_map>
#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 MOD 1000000007

int N, K;
LL cur, ans;
set<PR> S;

// returns the # of valid intervals with start positions in:
// (this interval's start, next interval's start]
LL Count(set<PR>::iterator I)
{
  // get key points from this interval and the next one
  int a = I->x + 1;
  I++;
  int b = I->x;
  int c = I->y - 1;
  // count intervals which start in [a, b] and end no later than c
  int v1 = c - b;
  int v2 = c - a;
  return (LL)(v1 + v2) * (v2 - v1 + 1) / 2;
}

// inserts interval [a, b] into the set, while updating the total # of valid intervals
void Insert(int a, int b)
{
  set<PR>::iterator I, J;
  I = S.lower_bound(mp(a, -1));
  // is the new interval obsolete (covers existing interval)?
  if (a <= I->x && I->y <= b)
    return;
  // erase any existing obsolete intervals (covering the new one)
  if (I->x > a)
    I--;
  for (;;)
  {
    if (I->y < b)
      break;
    J = I, I--;
    cur -= Count(J) + Count(I);
    S.erase(J);
    cur += Count(I);
  }
  // insert the new interval
  cur -= Count(I);
  S.insert(mp(a, b));
  cur += Count(I);
  I++;
  cur += Count(I);
}

LL ProcessCase()
{
  int i;
  // input
  Read(N), Read(K);
  // init
  S.clear();
  S.insert(mp(-1, -1));
  S.insert(mp(K, K + 1));
  ans = 1;
  cur = Count(S.begin());
  // process intervals
  Fox(i, N)
  {
    int s, d;
    Read(s), Read(d);
    Insert(s, s + d);
    ans = ans * (cur % MOD) % MOD;
  }
  return(ans);
}

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