Problem:


Score : 1100 points

Problem Statement

There is a set consisting of N distinct integers. The i-th smallest element in this set is S_i. We want to divide this set into two sets, X and Y, such that:

The absolute difference of any two distinct elements in X is A or greater.

The absolute difference of any two distinct elements in Y is B or greater.

How many ways are there to perform such division, modulo 10^9 + 7? Note that one of X and Y may be empty.

Constraints

All input values are integers.

1 ≦ N ≦ 10^5

1 ≦ A , B ≦ 10^{18}

0 ≦ S_i ≦ 10^{18}(1 ≦ i ≦ N)

S_i < S_{i+1}(1 ≦ i ≦ N - 1)

Input

The input is given from Standard Input in the following format:

N A B
S_1
:
S_N

Output

Print the number of the different divisions under the conditions, modulo 10^9 + 7.

Sample Input 1

5 3 7
1
3
6
9
12

Sample Output 1

5

There are five ways to perform division:

X={1,6,9,12}, Y={3}

X={1,6,9}, Y={3,12}

X={3,6,9,12}, Y={1}

X={3,6,9}, Y={1,12}

X={3,6,12}, Y={1,9}

Sample Input 2

7 5 3
0
2
4
7
8
11
15

Sample Output 2

4

Sample Input 3

8 2 9
3
4
5
13
15
22
26
32

Sample Output 3

13

Sample Input 4

3 3 4
5
6
7

Sample Output 4

0



Sample input:
5 3 7
1
3
6
9
12


Sample output:
5

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc009/tasks/agc009_c

A <= B としてよい
dpだろうなぁ

dpA[i][X] = 1つ前を置いたのがBで、Aに置かれた最大がindexXの時の置き方
dpB[i][X] = 同様

if S[i]-S[i-1] >= B:
    dpA[i][X] = dpA[i-1][X]
    if X == i-1:
        dpA[i][X] = ///


推移は、BITですればおｋ

もし差がB以下ならば→直前にBを置いていた場所に重ねおきはできない
→直前にAに置いていて、なおかつ最後にBに置いたのとの差がB以下の場合だけBにおける
→dpA[i][i-1]以外は0になる

"""

import sys
from sys import stdin
from collections import deque

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N,A,B = map(int,stdin.readline().split())
mod = 10**9+7

BITA = [0] * (N+20)
BITB = [0] * (N+20)
bitadd(1,1,BITA)
#bitadd(0,1,BITB)

aq = deque([])
bq = deque([])
Slis = [float("-inf")]

for loop in range(N):

    S = int(stdin.readline())
    
    aq.append( (S,loop+2) )
    bq.append( (S,loop+2) )
    while aq[0][0] <= S-A:
        aq.popleft()
    while bq[0][0] <= S-B:
        bq.popleft()

    #dpAへの推移(Bに置く)
    #Bに置けるのは、1つ前との差がB以上の場合全部おk
    #そうでない場合、前にAにおいていて、かつ差がB以上の場合

    #全てokの場合
    if S - Slis[-1] >= B:
        Aans = bitsum(N+2,BITB)
        Aans %= mod
    else: #そうでない場合→直前にAに置いていた場合のみ可能→bitをリセットする必要あり
        Aans = bitsum(bq[0][1]-1,BITB)
        Aans %= mod

    if S - Slis[-1] >= A:
        Bans = bitsum(N+2,BITA)
        Bans %= mod
    else:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod

    #if Aans < 0:
    #    Aans = 0
    #if Bans < 0:
    #    Bans = 0

    #print (Aans,Bans)
    #更新
    if S - Slis[-1] >= B:
        bitadd(loop+1,Aans,BITA)
    else:
        nowsum = bitsum(N+2,BITA)
        bitadd(1,-1*nowsum,BITA)
        bitadd(loop+1,Aans,BITA)

    if S - Slis[-1] >= A:
        bitadd(loop+1,Bans,BITB)
    else:
        nowsum = bitsum(N+2,BITB)
        bitadd(1,-1*nowsum,BITB)
        bitadd(loop+1,Bans,BITB)

    Slis.append(S)
    if len(Slis) >= 3 and Slis[-1] - Slis[-3] < min(A,B):
        print (0)
        sys.exit()

print ((bitsum(N+2,BITA) + bitsum(N+2,BITB))% mod)

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc009/tasks/agc009_c

A <= B としてよい
dpだろうなぁ

dpA[i][X] = 1つ前を置いたのがBで、Aに置かれた最大がindexXの時の置き方
dpB[i][X] = 同様

if S[i]-S[i-1] >= B:
    dpA[i][X] = dpA[i-1][X]
    if X == i-1:
        dpA[i][X] = ///


推移は、BITですればおｋ

もし差がB以下ならば→直前にBを置いていた場所に重ねおきはできない
→直前にAに置いていて、なおかつ最後にBに置いたのとの差がB以下の場合だけBにおける
→dpA[i][i-1]以外は0になる

"""

import sys
from sys import stdin
from collections import deque

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N,A,B = map(int,stdin.readline().split())
mod = 10**9+7

BITA = [0] * (N+20)
BITB = [0] * (N+20)
bitadd(1,1,BITA)
#bitadd(0,1,BITB)

aq = deque([])
bq = deque([])
Slis = [float("-inf")]

for loop in range(N):

    S = int(stdin.readline())
    
    aq.append( (S,loop+2) )
    bq.append( (S,loop+2) )
    while aq[0][0] <= S-A:
        aq.popleft()
    while bq[0][0] <= S-B:
        bq.popleft()

    #dpAへの推移(Bに置く)
    #Bに置けるのは、1つ前との差がB以上の場合全部おk
    #そうでない場合、前にAにおいていて、かつ差がB以上の場合

    #全てokの場合
    if S - Slis[-1] >= B:
        Aans = bitsum(N+2,BITB)
        Aans %= mod
    else: #そうでない場合→直前にAに置いていた場合のみ可能→bitをリセットする必要あり
        Aans = bitsum(bq[0][1]-1,BITB)
        Aans %= mod

    if S - Slis[-1] >= A:
        Bans = bitsum(N+2,BITA)
        Bans %= mod
    else:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod

    #if Aans < 0:
    #    Aans = 0
    #if Bans < 0:
    #    Bans = 0

    #print (Aans,Bans)
    #更新
    if S - Slis[-1] >= B:
        bitadd(loop+1,Aans,BITA)
    else:
        nowsum = bitsum(N+2,BITA)
        bitadd(1,-1*nowsum,BITA)
        bitadd(loop+1,Aans,BITA)

    if S - Slis[-1] >= A:
        bitadd(loop+1,Bans,BITB)
    else:
        nowsum = bitsum(N+2,BITB)
        bitadd(1,-1*nowsum,BITB)
        bitadd(loop+1,Bans,BITB)

    Slis.append(S)

print ((bitsum(N+2,BITA) + bitsum(N+2,BITB))% mod)

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc009/tasks/agc009_c

A <= B としてよい
dpだろうなぁ

dpA[i][X] = 1つ前を置いたのがBで、Aに置かれた最大がindexXの時の置き方
dpB[i][X] = 同様

if S[i]-S[i-1] >= B:
    dpA[i][X] = dpA[i-1][X]
    if X == i-1:
        dpA[i][X] = ///


推移は、BITですればおｋ

もし差がB以下ならば→直前にBを置いていた場所に重ねおきはできない
→直前にAに置いていて、なおかつ最後にBに置いたのとの差がB以下の場合だけBにおける
→dpA[i][i-1]以外は0になる

"""

import sys
from sys import stdin
from collections import deque

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N,A,B = map(int,stdin.readline().split())
mod = 10**9+7

BITA = [0] * (N+20)
BITB = [0] * (N+20)
bitadd(1,1,BITA)
#bitadd(0,1,BITB)

aq = deque([])
bq = deque([])
Slis = [float("-inf")]

for loop in range(N):

    S = int(stdin.readline())
    
    aq.append( (S,loop+2) )
    bq.append( (S,loop+2) )
    while aq[0][0] <= S-A:
        aq.popleft()
    while bq[0][0] <= S-B:
        bq.popleft()

    #dpAへの推移(Bに置く)
    #Bに置けるのは、1つ前との差がB以上の場合全部おk
    #そうでない場合、前にAにおいていて、かつ差がB以上の場合

    #全てokの場合
    if S - Slis[-1] >= B:
        Aans = bitsum(N+2,BITB)
        Aans %= mod
    else: #そうでない場合→直前にAに置いていた場合のみ可能→bitをリセットする必要あり
        Aans = bitsum(bq[0][1]-1,BITB)
        Aans %= mod

    if S - Slis[-1] >= A:
        Bans = bitsum(N+2,BITA)
        Bans %= mod
    else:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod

    if Aans < 0:
        Aans = 0
    if Bans < 0:
        Bans = 0

    #print (Aans,Bans)
    #更新
    if S - Slis[-1] >= B:
        bitadd(loop+1,Aans,BITA)
    else:
        nowsum = bitsum(N+2,BITA)
        bitadd(1,-1*nowsum,BITA)
        bitadd(loop+1,Aans,BITA)

    if S - Slis[-1] >= A:
        bitadd(loop+1,Bans,BITB)
    else:
        nowsum = bitsum(N+2,BITB)
        bitadd(1,-1*nowsum,BITB)
        bitadd(loop+1,Bans,BITB)

    Slis.append(S)

print ((bitsum(N+2,BITA) + bitsum(N+2,BITB))% mod)

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc009/tasks/agc009_c

A <= B としてよい
dpだろうなぁ

dpA[i][X] = 1つ前を置いたのがBで、Aに置かれた最大がindexXの時の置き方
dpB[i][X] = 同様

if S[i]-S[i-1] >= B:
    dpA[i][X] = dpA[i-1][X]
    if X == i-1:
        dpA[i][X] = ///


推移は、BITですればおｋ

もし差がB以下ならば→直前にBを置いていた場所に重ねおきはできない
→直前にAに置いていて、なおかつ最後にBに置いたのとの差がB以下の場合だけBにおける
→dpA[i][i-1]以外は0になる

"""

import sys
from sys import stdin
from collections import deque

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N,A,B = map(int,stdin.readline().split())
mod = 10**9+7

BITA = [0] * (N+20)
BITB = [0] * (N+20)
bitadd(1,1,BITA)
#bitadd(0,1,BITB)

aq = deque([])
bq = deque([])
Slis = [float("-inf")]

for loop in range(N):

    S = int(stdin.readline())
    
    aq.append( (S,loop+2) )
    bq.append( (S,loop+2) )
    while aq[0][0] <= S-A:
        aq.popleft()
    while bq[0][0] <= S-B:
        bq.popleft()

    #dpAへの推移(Bに置く)
    #Bに置けるのは、1つ前との差がB以上の場合全部おk
    #そうでない場合、前にAにおいていて、かつ差がB以上の場合

    #全てokの場合
    if S - Slis[-1] >= B:
        Aans = bitsum(N+2,BITB)
        Aans %= mod
    else: #そうでない場合→直前にAに置いていた場合のみ可能→bitをリセットする必要あり
        Aans = bitsum(bq[0][1]-1,BITB)
        Aans %= mod

    if S - Slis[-1] >= A:
        Bans = bitsum(N+2,BITA)
        Bans %= mod
    else:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod

    if Aans < 0:
        Aans = 0
    if Bans < 0:
        Bans = 0

    #print (Aans,Bans)
    #更新
    if S - Slis[-1] >= B:
        bitadd(loop+1,Aans,BITA)
    else:
        nowsum = bitsum(N+2,BITA)
        bitadd(1,-1*nowsum,BITA)
        bitadd(loop+1,Aans,BITA)

    if S - Slis[-1] >= A:
        bitadd(loop+1,Bans,BITB)
    else:
        nowsum = bitsum(N+2,BITB)
        bitadd(1,-1*nowsum,BITB)
        bitadd(loop+1,Bans,BITB)

    Slis.append(S)

print (bitsum(N+2,BITA) + bitsum(N+2,BITB) )

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect


class BinaryIndexedTree:

    def __init__(self, n, MOD):
        self.size = n + 1
        self.tree = [0] * (n + 2)
        self.MOD = MOD

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.MOD
            i += i & -i

    def debug_print(self, limit=None):
        if limit is None:
            limit = self.size
        acc = [0] + [self.sum(i) for i in range(limit)]
        aaa = [a1 - a0 for a0, a1 in zip(acc, acc[1:])]
        print(aaa)


def solve(n, a, b, sss):
    if a > b:
        a, b = b, a

    for s0, s2 in zip(sss, sss[2:]):
        if s2 - s0 < a:
            return 0

    MOD = 10 ** 9 + 7

    bit = BinaryIndexedTree(n, MOD)
    bit.add(0, 1)
    bit.add(1, 1)

    sss.insert(0, -10 ** 18 - 1)

    for i in range(1, n):
        s0 = sss[i]
        s1 = sss[i + 1]
        lim = bisect(sss, s1 - b) - 1
        bit.add(i + 1, bit.sum(lim))
        if s1 - s0 < a:
            bit.add(i - 1, -bit.sum(i - 1))

    return bit.sum(n)


n, a, b, *sss = map(int, sys.stdin.read().split())
print(solve(n, a, b, sss))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect
from collections import defaultdict


class BinaryIndexedTree:
    """ i = 1～n の範囲を受け取りつつ、0の番兵も許容する（全体を1ずらす） """

    def __init__(self, n):
        self.size = n + 1
        self.tree = [0] * (n + 2)

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def debug_print(self):
        acc = [self.sum(i) for i in range(self.size)]
        print(acc)
        acc = [0] + acc
        aaa = [a1 - a0 for a0, a1 in zip(acc, acc[1:])]
        print(aaa)


def solve(n, a, b, sss):
    if a > b:
        a, b = b, a

    for s0, s2 in zip(sss, sss[2:]):
        if s2 - s0 < a:
            return 0

    bit = BinaryIndexedTree(n)
    bit.add(0, 1)
    bit.add(1, 1)

    sss.insert(0, -10 ** 18 - 1)

    for i in range(1, n):
        s0 = sss[i]
        s1 = sss[i + 1]
        lim = bisect(sss, s1 - b) - 1
        bit.add(i + 1, bit.sum(lim))
        if s1 - s0 < a:
            bit.add(i - 1, -bit.sum(i - 1))

    return bit.sum(n)


n, a, b, *sss = map(int, sys.stdin.read().split())
print(solve(n, a, b, sss))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect
from collections import defaultdict


class BinaryIndexedTree:
    """ i = 1～n の範囲を受け取りつつ、0の番兵も許容する（全体を2ずらす） """

    def __init__(self, n):
        self.size = n + 1
        self.tree = [0] * (n + 2)

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def debug_print(self):
        acc = [self.sum(i) for i in range(1, self.size)]
        print(acc)
        acc = [0] + acc
        aaa = [a1 - a0 for a0, a1 in zip(acc, acc[1:])]
        print(aaa)


def solve(n, a, b, sss):
    if a > b:
        a, b = b, a

    for s0, s2 in zip(sss, sss[2:]):
        if s2 - s0 < a:
            return 0

    bit = BinaryIndexedTree(n)
    bit.add(0, 1)
    bit.add(1, 1)

    sss.insert(0, -10 ** 18)

    for i in range(1, n):
        s0 = sss[i]
        s1 = sss[i + 1]
        lim = bisect(sss, s1 - b, hi=i) - 1
        bit.add(i + 1, bit.sum(lim))
        if s1 - s0 < a:
            bit.add(i - 1, -bit.sum(i - 1))

    return bit.sum(n)


n, a, b, *sss = map(int, sys.stdin.read().split())
print(solve(n, a, b, sss))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(N, A, B, S):
    if N == 1:
        return 2
    INF = 1 << 62
    S = np.append(S, INF)
    if A > B:
        A, B = B, A
    if np.max(S[2:] - S[:-2]) < A:
        return 0
    # A 未満でたどって、Xがどこまで置けるか
    X = np.zeros_like(S)
    for i in range(1, N + 1):
        if S[i] - S[i - 1] >= A:
            X[i] = X[i - 1]
        else:
            X[i] = i
    # 直前の Y としてありうる最も右
    Y = np.searchsorted(S, S - B, side='right') - 1
    dp = np.zeros_like(S)
    dp_cum = np.zeros_like(S)

    dp[0] = 1
    dp_cum[0] = 1
    for n in range(1, N + 1):
        if X[n - 1] == 0:
            # 初出の Y
            dp[n] = 1
        # 直前の Y の範囲
        l, r = max(0, X[n - 1] - 1), min(n - 1, Y[n])
        if l <= r:
            dp[n] += dp_cum[r] - dp_cum[l] + dp[l]
        dp[n] %= MOD
        dp_cum[n] = (dp_cum[n - 1] + dp[n]) % MOD
    return dp[-1]

signature = '(i8,i8,i8,i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

N, A, B = map(int, readline().split())
S = np.array(read().split(), np.int64)

print(main(N, A, B, S))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n,x,y = map(int,input().split())
a = [int(input()) for i in range(n)]
mod = 10**9+7
bsx = [0]*n
bsy = [0]*n
rowx = [0]*n
rowy = [0]*n
for i in range(n):
  bsx[i] = bisect.bisect_right(a,a[i]-x)
  bsy[i] = bisect.bisect_right(a,a[i]-y)
  j = n-i-1
  if j == 0:
    continue
  if a[j-1]+x <= a[j]:
    rowx[j-1] += rowx[j]+1
  else:
    rowx[j-1] = 0
  if a[j-1]+y <= a[j]:
    rowy[j-1] += rowy[j]+1
  else:
    rowy[j-1] = 0
sm1 = [0 for i in range(n)]
sm2 = [0 for i in range(n)]
#sm1[i]: dp[i+1][i]
#sm2[i]: dp[i][i+1]
bit1 = Bit(n+2)
bit2 = Bit(n+2)
for i in range(n):
  if i == 0:
    sm1[i] = 1
    sm2[i] = 1
  else:
    sm1[i] = bit2.sum(min(i,bsx[i]+1))%mod
    sm2[i] = bit1.sum(min(i,bsy[i]+1))%mod
  bit1.add(i+1,sm1[i])
  bit1.add(i+rowx[i]+2,-sm1[i])
  bit2.add(i+1,sm2[i])
  bit2.add(i+rowy[i]+2,-sm2[i])
print(sm1[-1]+sm2[-1])

Submission status: Wrong Answer

Solution code:
#c
n,a,b = [int(i) for i in input().split()]
pos = [-10000000000000] #-inf
for _ in range(n):
    pos.append(int(input()))
    
a_list =[[0 for _ in range(n+1)] for _ in range(n+1)]
b_list =[[0 for _ in range(n+1)] for _ in range(n+1)]

a_list[0][1] = 1 #numbers. BA...A
b_list[0][1] = 1 #numbers  AB...B

for i in range(1,n):
    for j in range(0,i):
        if pos[i+1]-pos[i]>=a:
            a_list[j][i+1] += a_list[j][i]
        if pos[i+1]-pos[i]>=b:
            b_list[j][i+1] += b_list[j][i]
        if pos[i+1]-pos[j]>=b:
            b_list[i][i+1] += a_list[j][i]
        if pos[i+1]-pos[j]>=a:
            a_list[i][i+1] += b_list[j][i]

cnt = 0
for j in range(n):
    cnt += a_list[j][n]
    cnt += b_list[j][n]
        
print(cnt)

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i], B[i] = LI()
    cum = 0
    for i in range(N)[::-1]:
        cum +=(-(cum+A[i]))%B[i]
        #print(cum)

    ans = cum
    print(ans)
    return

def examB():
    N = I()
    V = [[]for _ in range(N)]
    for i in range(1,N):
        a = I()-1
        V[a].append(i)
    #print(V)
    dp = [0]*N
    def dfs(n,s):
        children = []
        for i in V[s]:
            child = dfs(n,i)
            children.append(child)
        rep = 0
        children.sort()
        for i,c in enumerate(children[::-1],start = 1):
            rep = max(rep,i+c)
        dp[s] = rep
        return rep
    ans = dfs(N,0)
    print(ans)
    return

def examC():
    class segment_():
        def __init__(self, A, n, segfunc, ide_ele=0):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            # qは含まない
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res

    N, A, B = LI()
    S = [I()for _ in range(N)]
    S.insert(0,-inf)
    #print(S)
    if A>B:
        A,B = B,A
    for i in range(N-1):
        if S[i+2]-S[i]<A:
            print(0)
            return
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1
    num = N+1
    L = [0] * num
    Seg_sum = segment_(L, num, lambda a, b: a + b)
    la = 0; lb = 0
    Seg_sum.update(0,1)
    Seg_sum.update(1,1)
    for i in range(1,N):
        while(lb<i and S[i+1]-S[lb+1]>=B):
            lb += 1
        dp[i+1] = Seg_sum.query(0,lb+1)
        Seg_sum.update(i+1,dp[i+1])
        #dp[i+1] = sum(dp[:lb+1])
        if S[i+1]-S[i]<A:
            for a in range(la,i):
                Seg_sum.update(a,0)
                dp[a] = 0
            la = i-1
        #print(dp)
    #print(dp)

    ans = sum(dp)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i], B[i] = LI()
    cum = 0
    for i in range(N)[::-1]:
        cum +=(-(cum+A[i]))%B[i]
        #print(cum)

    ans = cum
    print(ans)
    return

def examB():
    N = I()
    V = [[]for _ in range(N)]
    for i in range(1,N):
        a = I()-1
        V[a].append(i)
    #print(V)
    dp = [0]*N
    def dfs(n,s):
        children = []
        for i in V[s]:
            child = dfs(n,i)
            children.append(child)
        rep = 0
        children.sort()
        for i,c in enumerate(children[::-1],start = 1):
            rep = max(rep,i+c)
        dp[s] = rep
        return rep
    ans = dfs(N,0)
    print(ans)
    return

def examC():
    class segment_():
        def __init__(self, A, n, segfunc, ide_ele=0):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            # qは含まない
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res

    N, A, B = LI()
    S = [I()for _ in range(N)]
    S.insert(0,-inf)
    #print(S)
    if A>B:
        A,B = B,A
    for i in range(N-1):
        if S[i+2]-S[i]<A:
            print(0)
            return
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1
    num = N+1
    L = [0] * num
    Seg_sum = segment_(L, num, lambda a, b: a + b)
    la = 0; lb = -1
    Seg_sum.update(0,1)
    Seg_sum.update(1,1)
    for i in range(1,N):
        while(lb<i and S[i+1]-S[lb+1]>=B):
            lb += 1
        dp[i+1] = Seg_sum.query(0,lb+1)
        Seg_sum.update(i+1,dp[i+1])
        #dp[i+1] = sum(dp[:lb+1])
        if S[i+1]-S[i]<A:
            for a in range(la,i):
                Seg_sum.update(a,0)
                dp[a] = 0
            la = i
        #print(dp)
    #print(dp)

    ans = sum(dp)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

class Lazysegtree:
    #RUQ
    def __init__(self, A, intv, initialize = True, segf = min):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        self.lazy = [None]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, -1, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)

    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] is None:
                continue
            self.data[2*idx] = self.data[2*idx+1] = self.lazy[2*idx] \
            = self.lazy[2*idx+1] = self.lazy[idx] 
            self.lazy[idx] = None
            
            
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R)-1)
        
        s = self.intv                                                                   

        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def update(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = x
                self.lazy[R] = x
            if L & 1:
                self.data[L] = x
                self.lazy[L] = x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

inf = 10**19
N, A, B = map(int, readline().split())
if A > B:
    A, B = B, A
S = [-inf] + [int(readline()) for _ in range(N)]

MOD = 10**9+7
dpa = Lazysegtree([1] + [0]*N, 0, initialize = True, segf = lambda x, y: (x+y)%MOD)
dpb = Lazysegtree([1] + [0]*N, 0, initialize = True, segf = lambda x, y: (x+y)%MOD)

for i in range(1, N+1):
    oka = 0
    ng = i
    while abs(oka-ng) > 1:
        med = (oka+ng)//2
        if S[i] - S[med] >= A:
            oka = med
        else:
            ng = med

    okb = 0
    ng = i
    while abs(okb-ng) > 1:
        med = (okb+ng)//2
        if S[i] - S[med] >= B:
            okb = med
        else:
            ng = med
    
    dpa.update(i-1, i, dpb.query(0, oka+1))
    dpb.update(i-1, i, dpa.query(0, okb+1))
    if S[i] - S[i-1] < A:
        dpa.update(0, i-1, 0)
    if S[i] - S[i-1] < B:
        dpb.update(0, i-1, 0)
print((dpa.query(0, N+1) + dpb.query(0, N+1)) % MOD)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

INF = 10**18 + 100
N,A,B = map(int,input().split())
S = [-INF] + [int(x) for x in sys.stdin.read().split()]

MOD = 10**9 + 7

dpX = [0] * (N+1) # 最後にYを選んだとして、直前に選んだXがどこにあるか
dpY = [0] * (N+1) # 最後にXを選んだとして、直前に選んだYがどこにあるか
dpX[0] = 1
dpY[0] = 1
dpX_cum = [1] * (N+1) + [0]
dpY_cum = [1] * (N+1) + [0]
dpX_left = 0
dpY_left = 0
for n,x in enumerate(S[2:],2):
    iA = bisect_right(S,x-A)
    iB = bisect_right(S,x-B)
    # ....XY
    xy = dpY_cum[iB-1] - dpY_cum[dpY_left-1]
    # ....YX
    yx = dpX_cum[iA-1] - dpX_cum[dpX_left-1]
    # ....XX が不可能なら捨てる。明示的に捨てるのではなく、生きている番号だけ持つ
    if iA != n:
        dpY_left = n-1
    if iB != n:
        dpX_left = n-1
    dpX[n-1] = xy
    dpX_cum[n-1] = (dpX_cum[n-2] + xy) % MOD
    dpX_cum[n] = dpX_cum[n-1]
    dpY[n-1] = yx
    dpY_cum[n-1] = (dpY_cum[n-2] + yx) % MOD
    dpY_cum[n] = dpY_cum[n-1]

answer = dpX_cum[N-1] - dpX_cum[dpX_left-1]
answer += dpY_cum[N-1] - dpY_cum[dpY_left-1]
answer %= MOD
print(answer)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N,A,B=map(int,input().split())
inf,mod=float("inf"),10**9+7
S=[int(input()) for i in range(N)]
St_A=[0]*N
St_B=[0]*N
J_A,J_B=[0],[0]
for i in range(N):
  St_A[i]=bisect_left(S,S[i]+A)-1
  St_B[i]=bisect_left(S,S[i]+B)-1
  J_A.append(J_A[-1]+int(St_A[i]!=i))
  J_B.append(J_B[-1]+int(St_B[i]!=i))
  
#print(St_A,St_B)
#print(J_A,J_B)

dp_A=[0]*N
dp_B=[0]*N
dp_A[-1],dp_B[-1]=1,1
for i in range(N-1)[::-1]:
  if St_A[i]==i:
    dp_A[i]=(dp_A[i+1]+dp_B[i+1])%mod
  else:
    if J_B[St_A[i]]-J_B[i+1]==0:
      dp_A[i]=dp_B[St_A[i]]
    else:
      dp_A[i]=0
  if St_B[i]==i:
    dp_B[i]=(dp_A[i+1]+dp_B[i+1])%mod
  else:
    if J_A[St_B[i]]-J_A[i+1]==0:
      dp_B[i]=dp_A[St_B[i]]
    else:
      dp_B[i]=0
#print(dp_A)
#print(dp_B)
print(dp_A[0]+dp_B[0])

Submission status: Time Limit Exceeded

Solution code:
#c
n,a,b = [int(i) for i in input().split()]
pos = [-10**19] #-inf
for _ in range(n):
    pos.append(int(input()))
    
a_list =[[0 for _ in range(n+1)] for _ in range(n+1)]
b_list =[[0 for _ in range(n+1)] for _ in range(n+1)]

a_list[0][1] = 1 #numbers. BA...A
b_list[0][1] = 1 #numbers  AB...B

for i in range(1,n):
    for j in range(0,i):
        if pos[i+1]-pos[i]>=a:
            a_list[j][i+1] += a_list[j][i]
        if pos[i+1]-pos[i]>=b:
            b_list[j][i+1] += b_list[j][i]
        if pos[i+1]-pos[j]>=b:
            b_list[i][i+1] += a_list[j][i]
        if pos[i+1]-pos[j]>=a:
            a_list[i][i+1] += b_list[j][i]

cnt = 0
for j in range(n):
    cnt += a_list[j][n]
    cnt += b_list[j][n]
        
print(cnt)