CCCHK '15 S1 - Finding number of pairs

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.1s
Java 0.3s
Python 2 0.3s
Python 3 0.3s
Memory limit: 256M

Problem type

Given a sequence of n integers A[1], A[2], \dots, A[n] and a nonnegative integer M, count the number of pairs (i,j) that satisfy the following two conditions: i<j, and A[i]+A[j] \le M.

Input Specification

  • The first line contains integers n (2 \le n \le 10^5) and M (0 \le M \le 10^9), separated by a space.
  • The second line contains n integers, which denotes A[1], A[2], \dots, A[n] (0 \le A[i] \le 10^9).
  • In 50\% of the test cases, n \le 1000.

Output Specification

  • The output contains an integer, which denotes the number of pairs that satisfies the two conditions.
  • If the output is smaller than 10^9+7, please keep it as is. Otherwise, output the number mod 10^9+7.

Sample Input 1

5 6
1 2 3 4 5

Sample Output 1

6

Sample Input 2

5 12
3 6 8 2 8

Sample Output 2

7

Explanation: In Sample 1, among the pairs, (1,2), (1,3), (1,4), (1,5), (2,3), (2,4) satisfy the conditions. In Sample 2, (1,2), (1,3), (1,4), (1,5), (2,4), (3,4), (4,5) satisfy the conditions.


Comments


  • -3
    SagarSaha  commented on June 30, 2020, 6:41 p.m.

    Why is the time limit only 0.3s?


    • 3
      AlanL  commented on July 2, 2020, 11:34 a.m.

      So solutions like yours can't pass. Find a more efficient way to solve the problem.