Problem: We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).  The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.  You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.  You now have to take Q practical tests of your ability as a magical girl.  The i-th test will be conducted as follows:    * Initially, a piece is placed on the square where the integer L_i is written.    * Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.    * Here, it is guaranteed that R_i-L_i is a multiple of D.  For each test, find the sum of magic points consumed during that test.

Submission attempts (in order):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i


dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i


dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i


dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 6

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i


dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

import sys
input = sys.stdin.readline

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])



Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted