Problem:


Problem E: Rabbit Game Playing

Honestly, a rabbit does not matter.

There is a rabbit playing a stage system action game. In this game, every stage has a difficulty level. The rabbit, which always needs challenges, basically wants to play more difficult stages than he has ever played. However, he sometimes needs rest too. So, to compromise, he admitted to play T or less levels easier stages than the preceding one.

How many ways are there to play all the stages at once, while honoring the convention above? Maybe the answer will be a large number. So, let me know the answer modulo 1,000,000,007.

Input

The first line of input contains two integers N and T (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 10,000). N is the number of stages, and T is the compromise level.

The following N lines describe the difficulty levels of each stage. The i-th line contains one integer Di (1 ≤ Di ≤ 100,000), which is the difficulty level of the i-th stage.

Output

Calculate how many ways to play all the stages at once there are. Print the answer modulo 1,000,000,007 in a line.

Sample Input 1

3 1
1
2
3

Output for the Sample Input 1

4

Sample Input 2

5 3
9
2
6
8
8

Output for the Sample Input 2

24

Sample Input 3

5 7
9
9
9
1
5

Output for the Sample Input 3

48



Sample input:
3 1
1
2
3


Sample output:
4

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,t = LI()
    a = sorted([I() for _ in range(n)])
    r = 1
    i = 0
    for j in range(n):
        while a[i] < a[j] - t:
            i += 1
        r *= j-i+1
        r %= mod

    return r



print(main())

Submission status: Accepted

Solution code:
import sys
import bisect

# ???????????¨?????????DP?
# 

def main():
    n,t = map(int, sys.stdin.readline().split())
    levels = []
    for i in range(n):
        d = int(sys.stdin.readline())
        levels.append(d)
    levels.sort()

    ans = 1
    for i in range(n):
        cnt = i - bisect.bisect_left(levels, levels[i] - t) + 1
        ans *= cnt
        ans %= 1000000007

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 10**9+7
n, t = map(int, input().split())
d = [int(input()) for _ in range(n)]
d.sort(reverse=True)
c = Counter(d)
cum = [0 for _ in range(200002)]
for i in range(100000, 0, -1):
	cum[i] = cum[i+1] + c[i]
ans = 1
for i, x in enumerate(d):
	mul = i+1 - cum[x+t+1]
	ans *= mul
	ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
mod = 10**9+7
N,T = map(int,raw_input().split())
D = sorted(int(raw_input()) for i in xrange(N))
ans = 1
for i in xrange(N):
    ans = ans * (bisect.bisect_right(D[:i],D[i]) - bisect.bisect_left(D[:i],D[i]-T)+1) % mod
print ans