Assume we have fixed how many players will be in team \(A\), call it \(x\). Obviously team \(B\) must have \(N - x\) players. Let \(f(x)\) denote the number of possible divisions that respect these criteria.

Since we know how many players will be in each team, each player can then be part of one of \(4\) categories according to their \(L_i\) and \(R_i\):

• must be in team \(A\)
• must be in team \(B\)
• can be in either team
• cannot be in either team

Denote the number of players in these categories as \(a_x, b_x, c_x, d_x\) respectively. Note that if \(d_x > 0\) or \(x < a_x\), \(f(x) = 0\), otherwise \(f(x) = \dbinom {c_x} {x - a_x}\).

You’ll need to update \(a_x, b_x, c_x, d_x\) as you iterate through all \(x\) from \(1\) to \(N-1\), using e.g. arrays of arrays so that each player would only need to be updated \(O(1)\) times each, i.e. when he switches categories. With appropriate precalculation of factorials and inverses, this problem is solved in \(O(N)\).