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],\ldots ,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]\leq M.

Input specification:

  • The first line contains integer n\ (2 \leq n \leq 10^5) and M\ (0\leq M\leq 10^9), separated by a space.
  • The second line contains n integers, which denotes A[1],A[2],\ldots ,A[n]\ (0 \leq A[i] \leq 10^9)
  • In 50\% of the test cases, n \leq 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


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

    Why is the time limit only 0.3s?


    • 2
      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.