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: Accepted

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になる

#直前とB以上の差があるとき
if X != i-1:
    dpBに置く[i][最後にAに置いたのがX] = dpB[i-1][X]
else:
    dpB[i][i-1] = ΣdpA[i-1][y] (y<=S-B)
#差がないとき
if X == i-1:
    dpB[i][i-1] = ΣdpA[i-1][y] (y<=S-B)
else:
    dpB[i][X] = 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+3)
BITB = [0] * (N+3)
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(bq[0][1]-1,BITB)
        Aans %= mod
    else: #そうでない場合→直前にAに置いていた場合のみ可能→bitをリセットする必要あり
        Aans = bitsum(bq[0][1]-1,BITB)
        Aans %= mod

    if S - Slis[-1] >= A:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod
    else:
        Bans = bitsum(aq[0][1]-1,BITA)
        Bans %= mod
    """
    Aans = bitsum(bq[0][1]-1,BITB)
    Bans = bitsum(aq[0][1]-1,BITA)
    
    if Aans < 0:
        Aans = 0
    if Bans < 0:
        Bans = 0

    Aans %= mod
    Bans %= mod

    #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: Accepted

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)
    pos = 0

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

    return bit.sum(n)


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

Submission status: Accepted

Solution code:
mod=10**9+7

import bisect,sys

input=sys.stdin.readline

N,A,B=map(int,input().split())
S=[int(input()) for i in range(N)]

datax=[i for i in range(N+1)]
datay=[i for i in range(N+1)]

for i in range(2,N+1):
    if S[i-1]-S[i-2]>=A:
        datax[i]=datax[i-1]
    if S[i-1]-S[i-2]>=B:
        datay[i]=datay[i-1]

#print(datax)
#print(datay)

dpx=[0]*(N+1)
imosx=[0]*(N+1)
dpy=[0]*(N+1)
imosy=[0]*(N+1)
dpx[0]=1
dpy[0]=1
imosx[0]=1
imosy[0]=1

for i in range(1,N):
    id=bisect.bisect_right(S,S[i]-B)
    R=min(id+1,i)
    L=datax[i]
    if R>=L:
        dpx[i]=(imosy[R-1]-imosy[L-2]*(L>=2))%mod
        imosx[i]=(imosx[i-1]+dpx[i])%mod
    else:
        imosx[i]=imosx[i-1]

    id=bisect.bisect_right(S,S[i]-A)
    R=min(id+1,i)
    L=datay[i]
    if R>=L:
        dpy[i]=(imosx[R-1]-imosx[L-2]*(L>=2))%mod
        imosy[i]=(imosy[i-1]+dpy[i])%mod
    else:
        imosy[i]=imosy[i-1]

i=N

R=i
L=datax[i]
if R>=L:
    dpx[i]=(imosy[R-1]-imosy[L-2]*(L>=2))%mod
    imosx[i]=(imosx[i-1]+dpx[i])%mod
else:
    imosx[i]=imosx[i-1]

R=i
L=datay[i]
if R>=L:
    dpy[i]=(imosx[R-1]-imosx[L-2]*(L>=2))%mod
    imosy[i]=(imosy[i-1]+dpy[i])%mod
else:
    imosy[i]=imosy[i-1]

#print(dpx)
#print(dpy)
print((dpx[-1]+dpy[-1])%mod)

Submission status: Accepted

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.min(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: Accepted

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())
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
    
    tb = dpa.query(0, okb+1)
    dpa.update(i-1, i, dpb.query(0, oka+1))
    dpb.update(i-1, i, tb)
    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: Accepted

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] # -1
dpY_cum = [1] * (N+1) + [0] # -1
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] if iB >= dpY_left else 0
    # ....YX
    yx = dpX_cum[iA-1] - dpX_cum[dpX_left-1] if iA >= dpX_left else 0
    # ....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: Accepted

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])%mod)

Submission status: Runtime Error

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 A > B:
        A, B = B, A
    if np.max(S[2:] - S[:-2]) < A:
        return 0
    INF = 1 << 62
    S = np.append(S, INF)
    # 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: Runtime Error

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] - dpX_cum[dpX_left-1]
answer += dpY_cum[n] - dpY_cum[dpY_left-1]
answer %= MOD
print(answer)

dpX

Submission status: Runtime Error

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)
dpY_cum = [1] * (N+1)
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] - dpX_cum[dpX_left-1]
answer += dpY_cum[n] - dpY_cum[dpY_left-1]
answer %= MOD
print(answer)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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 = [0] * (N+1)
dpY_cum = [0] * (N+1)
dpX_cum[0] = 1
dpY_cum[0] = 1
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] - dpX_cum[dpX_left-1]
answer += dpY_cum[n] - dpY_cum[dpY_left-1]
answer %= MOD
print(answer)