Problem:
 Score : 900 points    Problem Statement Alice lives on a line. Today, she will travel to some place in a mysterious vehicle.
Initially, the distance between Alice and her destination is D . When she input a number x to the vehicle, it will travel in the direction of the destination by a distance of x if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than x .  Alice made a list of N numbers. The i -th number in this list is d_i . She will insert these numbers to the vehicle one by one.  However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after N moves.  She has Q plans to do this, as follows:   Rewrite only the q_i -th number in the list with some integer so that Alice will not reach the destination.   Write a program to determine whether each plan is feasible.      Constraints  1≤ N ≤ 5*10^5  1≤ Q ≤ 5*10^5  1≤ D ≤ 10^9  1≤ d_i ≤ 10^9(1≤i≤N)  1≤ q_i ≤ N(1≤i≤Q)  D and each d_i are integers.         Input Input is given from Standard Input in the following format:  N  D  d_1  d_2  ...  d_N  Q  q_1  q_2  ...  q_Q       Output Print Q lines. The i -th line should contain YES if the i -th plan is feasible, and NO otherwise.        Sample Input 1 4 10
3 4 3 3
2
4 3      Sample Output 1 NO
YES  For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO .
For the second plan, rewriting the third number in the list with 5 will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES .        Sample Input 2 5 9
4 4 2 3 2
5
1 4 2 3 5      Sample Output 2 YES
YES
YES
YES
YES  Alice will not reach the destination as it is, and therefore all the plans are feasible.       Sample Input 3 6 15
4 3 5 4 2 1
6
1 2 3 4 5 6      Sample Output 3 NO
NO
YES
NO
NO
YES

Solution (Python):
N,D=map(int,input().split())
d=list(map(int,input().split()))

dp=[D]*N

if abs(D-d[0])<D:
    dp[0]=abs(D-d[0])

for i in range(1,N):
    dp[i]=min(dp[i-1],abs(dp[i-1]-d[i]))

ans=["NO"]*N
data=[0]*(N+1)
for i in range(N-1,0,-1):
    if d[i]//2>data[i+1]:
        data[i]=data[i+1]
    else:
        data[i]=data[i+1]+d[i]
    if dp[i-1]>data[i+1]:
        ans[i]="YES"

i=0
if d[i]//2>data[i+1]:
    data[i]=data[i+1]
else:
    data[i]=data[i+1]+d[i]

if D>data[i+1]:
    ans[i]="YES"

Q=int(input())
q=list(map(int,input().split()))
for i in range(Q):
    print(ans[q[i]-1])

Solution (Python):
import sys
readline = sys.stdin.readline

N, D = map(int, readline().split())

A = list(map(int, readline().split())) + [0]

reach = [None]*(N+2)
reach[-1] = D
for i in range(N+1):
    r = reach[i-1]
    a = A[i]
    reach[i] = min(r, abs(r-a))

putter = [0]*(N+2)
for i in range(N, -1, -1):
    p = putter[i+1]
    a = A[i]
    if 2*p+1 >= a:
        p += a
    putter[i] = p

res = ['NO']*N
for i in range(N):
    if reach[i-1] > putter[i+1]:
        res[i] = 'YES'

Q = int(readline())
print('\n'.join(res[int(i)-1] for i in readline().split()))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    
    dn, s = MI()
    dd = LI()
    qn = II()
    qq = LI()
    qi = [(q - 1, i) for i, q in enumerate(qq)]
    
    pos = [s]
    for d in dd:
        pos.append(min(pos[-1], abs(d - pos[-1])))
    
    
    bb = [1] * (dn + 1)
    for i in range(dn - 1, -1, -1):
        d = dd[i]
        if d < bb[i + 1] * 2:
            bb[i] = bb[i + 1] + d
        else:
            bb[i] = bb[i + 1]
    
    
    
    
    
    
    ans = [""] * qn
    for q, ai in qi:
        if pos[q] >= bb[q + 1]: ans[ai] = "YES"
        else: ans[ai] = "NO"
    print(*ans, sep="\n")

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,X = map(int,readline().split())
D = [0] + list(map(int,readline().split()))
readline()
Q = list(map(int,read().split()))


start = [X] * (N+2)
for n,d in enumerate(D[1:],1):
    x = start[n]
    y = min(x, abs(x - d))
    start[n+1] = y


min_ng = [1] * (N+2)
for n in range(N,0,-1):
    d = D[n]
    x = min_ng[n+1]
    y = x + d
    if x + x <= d:
        y = x
    min_ng[n] = y

answer = ['YES' if x >= y else 'NO' for x,y in zip(start, min_ng[1:])]
print('\n'.join(answer[q] for q in Q))

Solution (Python):
import sys
input = sys.stdin.readline

"""
後ろから、到達不可能距離の集合を見ていきたい。
集合を持つと厳しいが、最小値だけ持っておけばよい。
"""

N,dist = map(int,input().split())
D = [int(x) for x in input().split()]


start_dist = [dist]
for d in D:
    x = start_dist[-1]
    y = x-d if x > d else d - x
    start_dist.append(x if x < y else y)

ng_dist = [None] * (N+1)
ng_dist[N] = 1

for i,d in enumerate(D[::-1]):
    x = ng_dist[N-i]
    y = x if x <= d//2 else x + d
    ng_dist[N-i-1] = y

input()
Q = [int(x) for x in input().split()]

answer = ['YES' if ng_dist[d] <= start_dist[d-1] else 'NO' for d in Q]

print('\n'.join(answer))

Solution (Python):
import sys
input = sys.stdin.readline

"""
後ろから、到達不可能距離の集合を見ていきたい。
集合を持つと厳しいが、最小値だけ持っておけばよい。
"""

N,dist = map(int,input().split())
D = [int(x) for x in input().split()]


start_dist = [dist]
for d in D:
    x = start_dist[-1]
    y = min(abs(x - d), x)
    start_dist.append(y)

ng_dist = [None] * (N+1)
ng_dist[N] = 1

for i,d in enumerate(D[::-1]):
    x = ng_dist[N-i]
    y = x if x <= d//2 else x + d
    ng_dist[N-i-1] = y

input()
Q = [int(x) for x in input().split()]

answer = ['YES' if ng_dist[d] <= start_dist[d-1] else 'NO' for d in Q]

print('\n'.join(answer))

Solution (Python):



def solve(n, d, da, q, qa):

    a = [d]
    x = d
    for di in da:
        x = min(x, max(x - di, di - x))
        a.append(x)

    b = [1]
    x = 1
    for i in range(n - 1, -1, -1):
        di = da[i]
        if di // 2 < x:
            x += di
        b.append(x)
    b.reverse()

    for qi in qa:
        if b[qi] <= a[qi - 1]:
            print('YES')
        else:
            print('NO')


def main():
    n, d = input().split()
    n = int(n)
    d = int(d)
    da = list(map(int, input().split()))
    q = input()
    q = int(q)
    qa = list(map(int, input().split()))

    solve(n, d, da, q, qa)

if __name__ == '__main__':
    main()

Solution (Python):
n, D = map(int, input().split())
x = list(map(int, input().split()))
Q = int(input())
q = list(map(int, input().split()))

ind = [D]
for i in range(n):
	ind.append(min(ind[-1], abs(ind[-1] - x[i])))

l = [1]
for i in range(n-1, -1, -1):
	if x[i] < 2*l[-1]:
		l.append(x[i] + l[-1])
	else:
		l.append(l[-1])
l = l[::-1]

for i in range(Q):
	if l[q[i]] <= ind[q[i]-1]:
		print("YES")
	else:
		print("NO")

Solution (Python):
n, D = map(int, input().split())
x = list(map(int, input().split()))
Q = int(input())
q = list(map(int, input().split()))

ind = [D]
for i in range(n):
	ind.append(min(ind[-1], abs(ind[-1] - x[i])))


l = [1]
for i in range(n-1, -1, -1):
	if x[i] < 2*l[-1]:
		l.append(x[i] + l[-1])
	else:
		l.append(l[-1])
l = l[::-1]

for i in range(Q):
	if l[q[i]] <= ind[q[i]-1]:
		print("YES")
	else:
		print("NO")

Solution (Python):
N, D = map(int, input().split())
ds = list(map(int, input().split()))
Q = int(input())
querys = list(map(lambda x: int(x) - 1, input().split()))


ps = [0] * (N + 1)
ps[0] = D
for i in range(N):
    ps[i + 1] = min(abs(ps[i] - ds[i]), ps[i])

if ps[N] != 0:
    print('\n'.join(['YES'] * Q))
    exit()


ms = [0] * (N + 1)
for i in range(N)[::-1]:
    if ms[i + 1] + 1 >= ds[i] - ms[i + 1]:
        ms[i] = ms[i + 1] + ds[i]
    else:
        ms[i] = ms[i + 1]

for q in querys:
    if ps[q] <= ms[q + 1]: 
        print('NO')
    else:
        print('YES')

Solution (Python):
N,start = map(int,input().split())
D = list(map(int,input().split()))
input()
Q = list(map(int,input().split()))

Q = [(k-1,i) for i,k in enumerate(Q)]
Q.sort()

P = [start]
for d in D:
  a = P[-1]
  b = abs(a-d)
  P.append(min(a,b))

result = [None]*len(Q)

x = 1

for i,d in zip(reversed(range(len(D))), reversed(D)):
  if Q[-1][0] == i:
    result[Q[-1][1]] = P[i] >= x
    Q.pop()
    if not Q:
      break

  if abs(x-d) < x:
    x += d

for r in result:
  print('YES' if r else 'NO')

Solution (Python):


import sys
import math

N,D = map(int, sys.stdin.readline().rstrip().split())
ds = list(map(int, sys.stdin.readline().rstrip().split()))
Q, = map(int, sys.stdin.readline().rstrip().split())
qs = list(map(int, sys.stdin.readline().rstrip().split()))


targets = [1]
for d in reversed(ds):
    if(d//2 < targets[-1]):
        targets.append(targets[-1] + d)
    else:
        targets.append(targets[-1])
targets.reverse()

current = D
can_avoids = []
for i in range(N):
    d = ds[i]
    target = targets[i+1]
    
    can_avoids.append(current >= target)
    if d//2 < current:
        current -= d
        current = max(-current, current)




for q in qs:
    if (can_avoids[q-1]):
        print("YES")
    else:
        print("NO")


exit(0)

Solution (Python):
N, D = map(int, input().split())
d = list(map(int, input().split()))
Q = int(input())
q = list(map(lambda x : int(x)-1 , input().split()))

dis = [0 for i in range(N+1)]
dis[0] = D
for i in range(N):
    dis[i+1] = min(dis[i], abs(dis[i] - d[i]))

dp = [0 for i in range(N+1)]
dp[N] = 1
for i in range(N-1, -1, -1):
    if d[i] // 2 >= dp[i+1]:
        dp[i] = dp[i+1]
    else:
        dp[i] = dp[i+1] + d[i]

for qi in range(Q):
    print(["YES", "NO"][dis[q[ qi ]] < dp[q[ qi ] + 1]])

Solution (Python):
N, D = map( int, input().split() )
d = list( map( int, input().split() ) )
Q = int( input() )
q = list( map( lambda x: int( x ) - 1, input().split() ) )

dis = [ 0 for i in range( N + 1 ) ]
dis[ 0 ] = D
for i in range( N ):
  dis[ i + 1 ] = min( dis[ i ], abs( dis[ i ] - d[ i ] ) )

dp = [ 0 for i in range( N + 1 ) ]
dp[ N ] = 1
for i in range( N - 1, -1, -1 ):
  if dp[ i + 1 ] <= d[ i ] // 2:
    dp[ i ] = dp[ i + 1 ]
  else:
    dp[ i ] = dp[ i + 1 ] + d[ i ]

for qi in range( Q ):
  print( [ "NO", "YES" ][ dis[ q[ qi ] ] >= dp[ q[ qi ] + 1 ] ] )

Solution (Python):
N, D = map( int, input().split() )
d = list( map( int, input().split() ) )
Q = int( input() )
q = list( map( lambda x: int( x ) - 1, input().split() ) )

dis = [ 0 for i in range( N + 1 ) ]
dis[ 0 ] = D
for i in range( N ):
  dis[ i + 1 ] = min( dis[ i ], abs( dis[ i ] - d[ i ] ) )

dp = [ 0 for i in range( N + 1 ) ]
dp[ N ] = 1
for i in range( N - 1, -1, -1 ):
  if dp[ i + 1 ] <= d[ i ] // 2:
    dp[ i ] = dp[ i + 1 ]
  else:
    dp[ i ] = dp[ i + 1 ] + d[ i ]

for qi in range( Q ):
  print( [ "NO", "YES" ][ dis[ q[ qi ] ] >= dp[ q[ qi ] + 1 ] ] )

Solution (Python):
N, D = map( int, input().split() )
d = list( map( int, input().split() ) )
Q = int( input() )
q = list( map( int, input().split() ) )

dis = [ 0 for i in range( N + 1 ) ]
dis[ 0 ] = D
for i in range( N ):
  dis[ i + 1 ] = min( dis[ i ], abs( dis[ i ] - d[ i ] ) )

dp = [ 0 for i in range( N + 1 ) ]
dp[ N ] = 1
for i in range( N - 1, -1, -1 ):
  if dp[ i + 1 ] <= d[ i ] // 2:
    dp[ i ] = dp[ i + 1 ]
  else:
    dp[ i ] = dp[ i + 1 ] + d[ i ]

for qi in range( Q ):
  print( [ "NO", "YES" ][ dis[ q[ qi ] - 1 ] >= dp[ q[ qi ] ] ] )

Solution (Python):

N, D = map(int, input().split())
dv = list(map(int, input().split()))
Q = int(input())
qv = list(map(int, input().split()))


dist_alice = D
dist_alice_list = [D]
for i in range(N):
    if dist_alice >= dv[i]:
        dist_alice -= dv[i]
    elif 2*dist_alice >= dv[i]:
        dist_alice = dv[i] - dist_alice
    dist_alice_list.append(dist_alice)

sol_min = [1]
sol_min_ = 1 
for i in range(N-1, -1, -1):
    if 2 * sol_min_ > dv[i]:
        sol_min_ += dv[i]
    sol_min.append(sol_min_)

for i in range(Q):
    if dist_alice_list[qv[i]-1] >= sol_min[N-qv[i]]:
        print("YES")
    else:
        print("NO")

Solution (Python):
N, D = list(map(int,input().split()))
d = list(map(int,input().split()))
Q = int(input())
q = list(map(int,input().split()))

a = [D for i in range(N)]
b = [1 for i in range(N+1)]
for i in range(1,N):
	a[i] = min(abs(a[i-1]-d[i-1]),a[i-1])
for i in range(N)[::-1]:
	if d[i]//2 < b[i+1]:
		b[i] = b[i+1] + d[i]
	else:
		b[i] = b[i+1]

res = ""
for i in q:
	if a[i-1] < b[i]:
		res+="NO"
	else:
		res+="YES"
	res+="\n"

print(res)

Solution (Python):
n, d = map(int, raw_input().split())
D = map(int, raw_input().split())
A = [0]*(n+1)
P = [0]*(n+1)

P[0] = pos = d
for i, x in enumerate(D):
    if x <= 2*pos:
        pos = abs(x-pos)
    P[i+1] = pos
    if pos == 0:
        break

for i in xrange(n-1, -1, -1):
    if D[i] <= 2*A[i+1]+1:
        A[i] = A[i+1] + D[i]
    else:
        A[i] = A[i+1]

q = input()
Q = map(int, raw_input().split())
for i in Q:
    if P[i-1] <= A[i] and pos == 0:
        print "NO"
    else:
        print "YES"