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



Sample input:
4 10
3 4 3 3
2
4 3


Sample output:
NO
YES

Submission status: Wrong Answer

Solution code:
n, d = [int(x) for x in input().split(" ")]

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

q = int(input())

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

A = [0]*n

currDist = d

before = True

done = False

for i in range(len(arr)):
    if done:
        A[i] = 0
    elif arr[i] < currDist*2 - 1:
        if arr[i] == currDist:
            done = True
            A[i] = 0
            currDist = 0
        elif arr[i] < currDist:
            A[i] = currDist - arr[i]
            currDist = A[i]
    else:
        A[i] = currDist

B = [0]*n

B[n-1] = 1

for i in range(n-1):
    j = n-2-i
    if arr[j] >= 2*B[j+1] - 1:
        B[j] = B[j+1]
    else:
        B[j] = B[j+1] + arr[j]

for i in range(q):
    pos = queries[i] - 1
    if pos == 0:
        print("YES" if (B[0] <= d) else "NO")
    else:
        print("YES" if (B[pos] <= A[pos-1]) else "NO")

Submission status: Wrong Answer

Solution code:
n, d = [int(x) for x in input().split(" ")]

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

q = int(input())

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

A = [0]*n

currDist = d

before = True

done = False

for i in range(len(arr)):
    if done:
        A[i] = 0
    elif arr[i] < currDist*2:
        if arr[i] == currDist:
            done = True
            A[i] = 0
            currDist = 0
        elif arr[i] < currDist:
            A[i] = currDist - arr[i]
            currDist = A[i]
    else:
        A[i] = currDist

B = [0]*n

B[n-1] = 1

for i in range(n-1):
    j = n-2-i
    if arr[j] >= 2*B[j+1]:
        B[j] = B[j+1]
    else:
        B[j] = B[j+1] + arr[j]

for i in range(q):
    pos = queries[i] - 1
    if pos == 0:
        print("YES" if (B[0] <= d) else "NO")
    else:
        print("YES" if (B[pos] <= A[pos-1]) else "NO")

Submission status: Wrong Answer

Solution code:
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 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))

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nd = raw_input()
nd = nd.split()
n,d = map(int,nd)

dl = raw_input()
dl = dl.split()
dl = map(int,dl)

q = raw_input()
q = int(q)

ql = raw_input()
ql = ql.split()
ql = map(int,ql)

x = [0]
status = 0
for i in range(n):
    if dl[i] >= 2 * abs(d-x[i]):
        x.append(x[i])
    elif x[i] > d:
        x.append(x[i] - dl[i])
    else:
        x.append(x[i] + dl[i])
    if x[i+1] == d:
        status = 1
        break

print x

if status == 0:
    for i in range(q):
        print "YES"
else:
    for i in range(q):
        if ql[i] >= len(x):
            print "NO"
        else:
            #到着できない回があれば1に
            flag = 0
            for j in range(abs(d-x[ql[i]-1])):
                if x[ql[i]-1] < d:
                    y = [x[ql[i]-1]+j]
                else:
                    y = [x[ql[i]-1]-j]
                #到着したら1に
                check = 0
                for k in range(n-ql[i]):
                    if dl[k+ql[i]] >= 2 * abs(d-y[k]):
                        y.append(y[k])
                    elif y[k] > d:
                        y.append(y[k] - dl[k+ql[i]])
                    else:
                        y.append(y[k] + dl[k+ql[i]])
                    if y[k+1] == d:
                        check = 1
                        break
                #print "j:",j," check:",check,y
                if check == 0:
                    flag = 1
                    break
            if flag == 1:
                print "YES"
            else:
                print "NO"

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nd = raw_input()
nd = nd.split()
n,d = map(int,nd)

dl = raw_input()
dl = dl.split()
dl = map(int,dl)

q = raw_input()
q = int(q)

ql = raw_input()
ql = ql.split()
ql = map(int,ql)

x = [0]
status = 0
for i in range(n):
    if dl[i] >= 2 * abs(d-x[i]):
        x.append(x[i])
    elif x[i] > d:
        x.append(x[i] - dl[i])
    else:
        x.append(x[i] + dl[i])
    if x[i+1] == d:
        status = 1
        break

print x

if status == 0:
    for i in range(q):
        print "YES"
else:
    for i in range(q):
        if ql[i] >= len(x):
            print "NO"
        else:
            #到着できない回があれば1に
            flag = 0
            for j in range(abs(d-x[ql[i]-1])):
                y = [x[ql[i]-1]+j]
                #到着したら1に
                check = 0
                for k in range(n-ql[i]):
                    if dl[k+ql[i]] >= 2 * abs(d-y[k]):
                        y.append(y[k])
                    elif y[k] > d:
                        y.append(y[k] - dl[k+ql[i]])
                    else:
                        y.append(y[k] + dl[k+ql[i]])
                    if y[k+1] == d:
                        check = 1
                        break
                #print "j:",j," check:",check,y
                if check == 0:
                    flag = 1
                    break
            if flag == 1:
                print "YES"
            else:
                print "NO"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
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(sorted(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]
    #print("current:", current)
    can_avoids.append(current >= target)
    if d//2 < current:
        current -= d
        current = max(-current, current)

#print(targets)
#print(can_avoids)

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


exit(0)

Submission status: Wrong Answer

Solution code:
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]])

Submission status: Wrong Answer

Solution code:
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(0, 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 i in range(Q):
    print(["YES", "NO"][dis[q[i]] <= dp[q[i] + 1]])

Submission status: Wrong Answer

Solution code:
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] <= 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]:
        print "NO"
    else:
        print "YES"

Submission status: Wrong Answer

Solution code:
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] <= A[i+1]+1:
        A[i] = A[i+1] + D[i]
    else:
        A[i] = 0

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nd = raw_input()
nd = nd.split()
n,d = map(int,nd)

dl = raw_input()
dl = dl.split()
dl = map(int,dl)

q = raw_input()
q = int(q)

ql = raw_input()
ql = ql.split()
ql = map(int,ql)

x = [0]
status = 0
for i in range(n):
    if dl[i] >= 2 * abs(d-x[i]):
        x.append(x[i])
    elif x[i] > d:
        x.append(x[i] - dl[i])
    else:
        x.append(x[i] + dl[i])
    if x[i+1] == d:
        status = 1
        break

#print x

if status == 0:
    for i in range(q):
        print "YES"
else:
    for i in range(q):
        if ql[i] >= len(x):
            print "NO"
        else:
            #到着できない回があれば1に
            flag = 0
            for j in range(abs(d-x[ql[i]-1])):
                if x[ql[i]-1] < d:
                    y = [x[ql[i]-1]+j]
                else:
                    y = [x[ql[i]-1]-j]
                #到着したら1に
                check = 0
                for k in range(n-ql[i]):
                    if dl[k+ql[i]] >= 2 * abs(d-y[k]):
                        y.append(y[k])
                    elif y[k] > d:
                        y.append(y[k] - dl[k+ql[i]])
                    else:
                        y.append(y[k] + dl[k+ql[i]])
                    if y[k+1] == d:
                        check = 1
                        break
                #print "j:",j," check:",check,y
                if check == 0:
                    flag = 1
                    break
            if flag == 1:
                print "YES"
            else:
                print "NO"

Submission status: Time Limit Exceeded

Solution code:
N,D = list(map(int,input().split()))
Dlist = list(map(int,input().split()))
Q = int(input())
Qlist = list(map(int,input().split()))


def testOneQ(distance, dList, Qnumber):

	for d in dList[:Qnumber-1]:
		distance = min(distance, abs(distance-d) )

	if distance == 0:
		return "NO"

	for newDistance in range(1,distance+1):
		zeroFlag = False
		newD = newDistance
		for d in dList[Qnumber:]:
			newD = min(newD, abs(newD-d))
			if newD == 0:
				zeroFlag = True
		if not zeroFlag:
			return "YES"
	return "NO"

for q in Qlist:
	print( testOneQ(D,Dlist,q) )

Submission status: Accepted

Solution code:
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])


#print(dp)
#print(data)
#print(ans)

Submission status: Accepted

Solution code:
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()))

Submission status: Accepted

Solution code:
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():
    # YouTubeの通り
    dn, s = MI()
    dd = LI()
    qn = II()
    qq = LI()
    qi = [(q - 1, i) for i, q in enumerate(qq)]
    # pos[i]...dd[i]の移動前の位置
    pos = [s]
    for d in dd:
        pos.append(min(pos[-1], abs(d - pos[-1])))
    # print(pos)
    # bb[i]...dd[i]の移動前にこの距離以上の位置にいればゴールに届かないという境目
    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]
    # print(bb)
    #    dd0   dd1   dd2   dd3
    # po0   po1   po2   po3   po4
    # bb0   bb1   bb2   bb3   bb4
    # という前後関係なのでq番目(0-origin)のddに魔法をかけるときは
    # pos[q]>=bb[q+1]であるなら妨害可能(YES)
    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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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])))
#print(ind)

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")

Submission status: Accepted

Solution code:
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[i]: i回目の移動後の位置（目的地までの距離）
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[i]: i番目の移動後にm以下の位置ならば全て、目的地に到達可能であるようなmの最大値
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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
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]
    #print("current:", current)
    can_avoids.append(current >= target)
    if d//2 < current:
        current -= d
        current = max(-current, current)

#print(targets)
#print(can_avoids)

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


exit(0)

Submission status: Accepted

Solution code:
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]])

Submission status: Accepted

Solution code:
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 ] ] )

Submission status: Accepted

Solution code:
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 ] ] ] )

Submission status: Accepted

Solution code:
# E
N, D = map(int, input().split())
dv = list(map(int, input().split()))
Q = int(input())
qv = list(map(int, input().split()))

# trace of Alice
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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"

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("E.in", "r", stdin);
	freopen ("E.out", "w", stdout);
#endif
}

const int N = 5e5 + 1e3;

int n, d[N], pre[N], f[N];

int main () {

	File();

	n = read(); pre[0] = read(); f[n + 1] = 1;

	For (i, 1, n) 
		pre[i] = min(pre[i - 1], abs(pre[i - 1] - (d[i] = read())));
	Fordown (i, n, 1) 
		f[i] = f[i + 1] + ((f[i + 1] << 1) > d[i] ? d[i] : 0);

	For (i, 1, read()) {
		int x = read();
		puts(pre[x - 1] >= f[x + 1] ? "YES" : "NO");
	}

	return 0;

}

Submission status: Runtime Error

Solution code:
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')

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

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


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]
    #print("current:", current)
    can_avoids.append(current >= target)
    if d//2 < current:
        current -= d
        current = max(-current, current)

#print(targets)
#print(can_avoids)

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


exit(0)