Overview

This problem asks us to count the pairs of points such that the slope of the line passing through them is at least \(A\) and at most \(B\). By transforming the coordinates, we can rephrase the condition into “both values are in non-decreasing order,” which allows us to count the pairs efficiently using sorting and a Fenwick Tree (BIT).

Analysis

Checking All Pairs Is Too Slow

Calculating the slope for all pairs of points takes \(O(N^2)\) time. For \(N \le 10^5\), the number of pairs can be up to about \(5 \times 10^9\), which will not run within the time limit.

Furthermore, computing slopes using floating-point numbers can introduce precision issues when comparing with the boundaries \(A\) and \(B\). Therefore, we rewrite the condition without using division.

Rephrasing the Slope Condition via Coordinate Transformation

First, consider the case where \(A < B\).

When counting pairs of points, the order of their original indices is not essential. Since swapping the two points does not change the slope between them, we can assume without loss of generality that \(X_i < X_j\).

Since \(X_j-X_i>0\), the condition can be rewritten as:

\(A(X_j-X_i) \le Y_j-Y_i \le B(X_j-X_i)\)

Rearranging the left and right inequalities respectively gives:

• \(Y_i-AX_i \le Y_j-AX_j\)
• \(BX_i-Y_i \le BX_j-Y_j\)

Thus, for each point, if we define:

\(U_i=Y_i-AX_i,\qquad V_i=BX_i-Y_i\)

the desired condition becomes:

\(U_i \le U_j \quad \text{and} \quad V_i \le V_j\)

Conversely, if these two inequalities hold, then since:

\(U_i+V_i=(B-A)X_i\)

we have \(X_i \le X_j\). Since \(A<B\) and distinct points have distinct \(X\)-coordinates, in fact \(X_i<X_j\) holds. Therefore, the transformed condition is equivalent to the original slope condition.

Sorting by One Coordinate and Counting the Other

We sort the transformed points \((U_i,V_i)\) in ascending order of \(U_i\), breaking ties in ascending order of \(V_i\).

When processing points in this order, all points processed prior to the current point have a \(U\) less than or equal to that of the current point. Therefore, the number of valid pairs formed with the current point is:

“the number of previously processed points whose \(V\) is less than or equal to the current point’s \(V\).”

For example, if the already processed \(V\)-values are \([1,4,4]\) and the current \(V\) is \(4\), the number of pairs to add is \(3\).

Finding this count by scanning linearly each time would again take \(O(N^2)\) time, so we use a Fenwick Tree.

When \(A=B\)

When \(A=B\), we count pairs whose slope is exactly \(A\).

This is equivalent to:

\(Y_j-Y_i=A(X_j-X_i)\)

which means:

\(Y_i-AX_i=Y_j-AX_j\)

Therefore, we only need to count pairs of points with equal \(Y_i-AX_i\), which can be handled simply using a dictionary (hash map).

Algorithm

When \(A=B\)

Maintain the frequency of each value using a dictionary.

For each point \((x,y)\), perform the following:

1. Calculate \(t=y-Ax\).
2. Add the number of times \(t\) has appeared so far to the answer.
3. Increment the frequency of \(t\) by \(1\).

If the same value has already appeared \(c\) times, \(c\) new pairs can be formed with the current point.

When \(A<B\)

1. Transform each point into \((U,V)=(Y-AX,\ BX-Y)\).
2. Sort the points in lexicographical order of \((U,V)\).
3. Coordinate compress the \(V\) values.
   • Sort the distinct values of \(V\) in ascending order and assign ranks \(1,2,\dots,M\).
   • This preserves the relative order so that they can be used as indices for the Fenwick Tree.
4. Initialize the Fenwick Tree with all \(0\)s.
5. Process each point in sorted order:
   • Let \(r\) be the rank of the current \(V\).
   • Query the Fenwick Tree for the sum of counts from rank \(1\) to \(r\), and add it to the answer.
   • Increment the count at rank \(r\) by \(1\).
6. Output the answer.

A Fenwick Tree is a data structure that can perform each of the following operations in \(O(\log N)\) time:

• Add a value at a specified position.
• Compute the sum from the beginning up to a specified position.

Each pair is counted only when processing the point that appears later in the sorted order, so no pair is counted more than once.

Complexity

• Time complexity: \(O(N\log N)\) when \(A<B\), and \(O(N)\) when \(A=B\) assuming dictionary operations take \(O(1)\) on average
• Space complexity: \(O(N)\)

Implementation Notes

• Sort in ascending order of \(V\) when \(U\) are equal.
  Pairs with \(U_i=U_j\) can also satisfy the condition. By processing points with smaller \(V\) first, such pairs can be counted correctly. In Python, calling points.sort() on a list of tuples sorts them in this order by default.

• Include the current rank in the prefix sum query.
  The condition is \(V_i\le V_j\), not \(V_i<V_j\). In the code, we query the sum up to rank inclusive.

• Add the current point after querying.
  If it is added before the query, the point would form a pair with itself and be counted.

• Use 1-based indexing for the Fenwick Tree.
  The expression i & -i in the code is used to find the next index to visit when updating or computing prefix sums.

• Be mindful of integer sizes.
  \(AX\) and \(BX\) can have absolute values up to \(10^{18}\), and the answer can be up to \(\frac{N(N-1)}{2}\). While Python handles arbitrarily large integers automatically, other languages will require 64-bit integers.

  Source Code

import sys


def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(it)
    a = next(it)
    b = next(it)

    if a == b:
        counts = {}
        ans = 0
        for x, y in zip(it, it):
            value = y - a * x
            count = counts.get(value, 0)
            ans += count
            counts[value] = count + 1
        print(ans)
        return

    points = [(y - a * x, b * x - y) for x, y in zip(it, it)]
    points.sort()

    values = sorted({v for _, v in points})
    ranks = {v: i for i, v in enumerate(values, 1)}
    m = len(values)
    bit = [0] * (m + 1)
    ans = 0

    for _, v in points:
        rank = ranks[v]
        i = rank
        while i:
            ans += bit[i]
            i -= i & -i

        i = rank
        while i <= m:
            bit[i] += 1
            i += i & -i

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.