Submission #856697

---

Source Code Expand

n = int(raw_input())
har = map(int , raw_input().split())
L = int(raw_input())
q = int(raw_input())

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])
 
 
def s_p(g, start, end):
    parents = {}
    for parent, child in bfs(g, start):
        parents[child] = parent
        if child == end:
            revpath = [end]
            while True:
                parent = parents[child]
                revpath.append(parent)
                if parent == start:
                    break
                child = parent
            return list(reversed(revpath))
    return None # or raise appropriate exception

graph = {i:[] for i in xrange(n)}
for i in xrange(n):
    if i - 1 >= 0:graph[i].append(i-1)
    if i + 1 <= n-1:graph[i].append(i+1)
for i in xrange(q):
    a,b = map(int , raw_input().split())
    a-=1
    b-=1
    path = s_p(graph,a,b)
    ans = 0
    sm = 0
    #print path
    pre = har[path[0]]
    psm = 0
    cost = []
    pp = 0
    for ix in xrange(1,len(path)):
        sm += abs(har[path[ix]] - pre)
        psm += abs(har[path[ix]] - pre)
        pre = har[path[ix]]
        if sm > L:
          ans += 1
          sm -= pp
        if sm == L:
          sm = 0
          ans += 1
        cost.append(sm)
        pp = sm
    if sm > 0:
        ans += 1
    print ans
        

Submission Info

Judge Result