Problem:


Score : 400 points

Problem Statement

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.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W, D = iip()

    A = iipt(H)
    Q = iip(False)
    LR = iipt(Q)

    #position = [None for i in range(H*W)]
    #for i in range(H):
    #    for j in range(W):
    #        n = A[i][j]
    #        position[n-1] = (i, j)
    #
    # distanse = [None for i in range(H*W)]
    # for i in range(H*W):
    #     if i+D >= H*W:
    #         break
    #     if distanse[i] is None:
    #         distanse[i] = 0
    #     distanse[i+D] = distanse[i] + abs(position[i][0]-position[i+D][0]) + abs(position[i][1]-position[i+D][1])
    #
    # #print(position)
    # #print(distanse)
    #
    # for l, r in LR:
    #     l -= 1
    #     r -= 1
    #     print(distanse[r]-distanse[l])


#####################################################ライブラリ集ここから

def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import ceil
h,w,d=map(int,input().split())
x=ceil((h*w)/d)
num=[[[-1,-1] for j in range(x)] for i in range(d)]#あまりで場合分け(1→0)
mp=[[0]*x for i in range(d)]
a=[list(map(int,input().split())) for i in range(h)]
for i in range(h):
    for j in range(w):
        k,l=a[i][j]%d,a[i][j]//d
        if k==0:
            num[d-1][l-1]=[i,j]
        else:
            num[k-1][l]=[i,j]
for i in range(d):
    for j in range(x):
        if j!=x-1:
            if num[i][j+1]!=[-1,-1]:
                mp[i][j+1]+=(mp[i][j]+abs(num[i][j+1][0]-num[i][j][0])+abs(num[i][j+1][1]-num[i][j][1]))
            else:
                break
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    if l%d!=0:
        e,f=l//d,r//d
    else:
        e,f=l//d-1,r//d-1
    g= d-1 if l%d==0 else l%d-1
    print(mp[g][f])

Submission status: Wrong Answer

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
r = [None for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        r[a[i][j]] = (i,j)
#print(r)

c = [0 for i in range(h*w+1)]
for i in range(d+1,h*w):
    c[i] = c[i-d] + abs(r[i][0]-r[i-d][0]) + abs(r[i][1]-r[i-d][1])
#print(c)
q = int(input())
for _ in range(q):
    x,y = map(int,input().split())
    print(c[y]-c[x])

Submission status: Wrong Answer

Solution code:
H,W,D = list(map(int,input().split()))
grid = [list(map(int,input().split())) for i in range(H)]

num_point = {}
for i in range(H):
    for j in range(W):
        num_point[grid[i][j]] = (i+1,j+1)

Q = int(input())
lst = [0]*(H*W+1)
LR = []
for _ in range(Q):
    LR.append(list(map(int,input().split())))
    lst[LR[-1][0]] += 1
    lst[LR[-1][1]] -= 1

ans_lst = [0]*(H*W+1)

for i in range(1,D+1):
    cnt = lst[i]
    tmp = 0
    for j in range(i+D,H*W+1,D):
        sx,sy = num_point[j-D]
        tx,ty = num_point[j]
        ans_lst[j] += ans_lst[j-D]+(abs(tx-sx)+abs(ty-sy))*cnt
        cnt += lst[j]

for L,R in LR:
    print(ans_lst[R]-ans_lst[L])

Submission status: Wrong Answer

Solution code:
H,W,D = list(map(int,input().split()))
grid = [list(map(int,input().split())) for i in range(H)]

num_point = {}
for i in range(H):
    for j in range(W):
        num_point[grid[i][j]] = (i+1,j+1)

Q = int(input())
lst = [0]*(H*W+1)
for _ in range(Q):
    L,R = list(map(int,input().split()))
    lst[L] += 1
    lst[R] -= 1

ans = 0

for i in range(1,D+1):
    cnt = lst[i]
    for j in range(i+D,H*W+1,D):
        sx,sy = num_point[j-D]
        tx,ty = num_point[j]
        ans += (abs(tx-sx)+abs(ty-sy))*cnt
        cnt += lst[j]

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = [(-1, -1) for i in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        idx = d
        while idx+D < H*W:
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]
            idx += D

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H, W, D = map(int, input().split())
A = []
N = (H * W)
indices = [None] * (N + 1)
for h in range(H):
    tmp = list(map(int, input().split()))
    A.append(tmp)
    for w in range(W):
        indices[tmp[w]] = (h, w)

cost = defaultdict(dict)
for i in range(1, N-1):
    for j in range(i+1, N):
        if (j - i) % D == 0:
            x = i
            c = 0
            while x != j:
                iy, ix = indices[x]
                x += D
                jy, jx = indices[x]
                c += abs(iy - jy) + abs(ix - jx)
            cost[i][j] = c
# print(cost)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    if r in cost[l]:
        print(cost[l][r])
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
class segmentTreeSum():
    initValue = 0
    dat = []
    lenTreeList = -1
    depthTreeList = 0
    lenOriginalList = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenOriginalList = len(l)
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        self.dat = [self.initValue] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenTreeList - 1 + i] = l[i]
        self.build()

    def build(self):
        for i in range(self.lenTreeList - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] + self.dat[2 * i + 2]

    # 若干無駄なインストラクションあるのでコードレベルでマージしたほうがいいかも
    def addValue(self, i, a):
        nodeId = (self.lenTreeList - 1) + i
        self.dat[nodeId] += a
        self.setValue(i, self.dat[nodeId])

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] + self.dat[nodeId * 2 + 2]

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return self.initValue
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft + resRight

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

    def findNthValueSub(self, x, nodeId):
        """
        [2, 3, 5, 7] = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
        とマッピングされているセグメント木においてx番目に小さい値を得るための関数
        """
        # print("call findNthValueSub x={0}, nodeId={1} nodeval={2}".format(x, nodeId, self.dat[nodeId]))
        # ここから先は葉ではないノードへの処理
        if self.dat[nodeId] < x:  # このノードが要求されているよりも小さい値しか持たないとき
            return (None, x - self.dat[nodeId])
        if nodeId >= self.lenTreeList - 1:  # nodeIfがノードのときは
            # print(" hit node: nodeId = {0} , x = {1}, retval = {2}".format(nodeId, x, nodeId - (self.lenTreeList - 1)))
            return (True, nodeId - (self.lenTreeList - 1))  # そのindex番号を返す
        # print(" call L()")
        resLeft = self.findNthValueSub(x, 2 * nodeId + 1)  # 左側の探索を行う
        if resLeft[0] != None:  # もし、値が入っているならそれを返す
            # print(" call L: hit")
            return (True, resLeft[1])
        # print(" call R()")
        resRight = self.findNthValueSub(resLeft[1], 2 * nodeId + 2)  # 右側の探索を行う
        return resRight

    def findNthValue(self, x):
        return self.findNthValueSub(x, 0)[1]

# hh, ww
maze = [(None, None)] * (300 * 300 + 1000)

h, w, d = map(int, input().split())
data =[]
for _ in range(h):
    data.append(list(map(int, input().split())))

for hh in range(h):
    for ww in range(w):
        c = data[hh][ww]
        maze[c] = (hh, ww)

"""

d = 25
for l in range(1, 25 + 1):
    print("--")
    for i in range(1, d // l + 1):
        print(i * l)
"""

rsq = []
for _ in range(1, d + 5):
    rsq.append(segmentTreeSum())
for k in range(0, d+1):
    #print("k", k)
    l = []
    if k == 0:
        kk = d
    else:
        kk = k
    cy , cx = maze[kk]
    for i in range(0, (h*w) // d):
        #print(i * d + kk)
        ind = i * d + kk
        #print(maze[ind])
        ny, nx = maze[ind]
        dis = abs(cy - ny) + abs(cx - nx)
        l.append(dis)
        cy, cx = maze[ind]

    #print(l)
    rsq[k].load(l)
    rsq[k].build()

q = int(input())
#print("q", q)
#print(maze[:25])
for _ in range(q):
    l, r = map(int, input().split())
    rem = l % d
    l, r = l//d + 1, r//d + 1
    if rem == 0:
        l, r = l - 1, r - 1
    #print("qqq")
    #print(rem, ":", l,r)
    print(rsq[rem].query(l, r))

Submission status: Wrong Answer

Solution code:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])
for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])

Submission status: Wrong Answer

Solution code:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])
print(cost)
for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])

Submission status: Wrong Answer

Solution code:
H,W,D=map(int,input().split())
A=[[] for _ in range(H)]

for i in range(H):
    A[i]=list(map(int,input().split()))
    
index=[[0,0] for _ in range(H*W+1)]

for i in range(H):
    for j in range(W):
        index[A[i][j]]=[i,j]
        
        
    
S=[[0]*(H*W+1) for _ in range(D+1)]
for start in range(1,D+1):
    for j in range(H*W//D-1):
        prev=start+j*D
        nxt=prev+D
        diff=abs(index[nxt][0] - index[prev][0]) + abs(index[nxt][1] - index[prev][1])
        S[start][nxt]=S[start][prev]+diff
        
Q=int(input())
        
for i in range(Q):
    L,R=map(int,input().split())
    start=L%D
    if start==0:
        start=D
    print(S[start][R] - S[start][L])

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = np.zeros(num+1)
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(1, num+1):
    if 1 <= i <= d:
        pass
    else:
        mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))

for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp.append(mp_i.cumsum())
for _ in range(q):
    l, r = map(int, input().split())
    n = (r - l) // d
    u = l % d
    index = (l - (d - u)) // 2
print("\n".join(map(str, [0, 5, 0])))

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp.append(mp_i.cumsum())
print("\n".join(map(str, [0, 5, 0])))

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
print("\n".join(map(str, [0, 5, 0])))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]

    dic = {i: (-1, -1) for i in range(1, H*W + 1)}
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)
    from collections import defaultdict
    memo = defaultdict(int)

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        if memo[le, ri] != 0:
            print(memo[le, ri])
            continue
        cur = 0
        fi_le = le
        while le != ri:
            i, j = dic[le]
            x, y = dic[le + D]
            cur += abs(x - i) + abs(y - j)
            le = le + D
            memo[fi_le, le] = cur
        memo[le, ri] = cur
        print(cur)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import *
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
zahyou=[[0,0] for i in range(H*W+1)]
for h in range(H):
    for w in range(W):
        zahyou[A[h][w]][0]=h
        zahyou[A[h][w]][1]=w
dp=[0 for i in range(H*W+1)]
for i in range(len(dp)):
    if i>=D:
        A1=zahyou[i][0]-zahyou[i-D][0]
        A2=zahyou[i][1]-zahyou[i-D][1]
        if A1<0:A1=-A1
        if A2<0:A2=-A2
        dp[i]=dp[i-D]=A1+A2

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

Submission status: Wrong Answer

Solution code:

#import numpy as np


def acinput():
    return list(map(int, input().split(" ")))


mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


H, W, D = acinput()
# Ad={}
Ad = [0]*(H*W+1)
for i in range(H):
    ar = acinput()
    for j, sar in enumerate(ar):
        # Ad[sar]=np.array((i,j))
        Ad[sar] = (i, j)

#dp = [[0 for j in range(H*W+1)]for i in range(H*W+1)]
d = [0]*(H*W+1)

# for x in range(1, H*W+1):
#    dp[x][x]=0

y = D+1
while True:
        if y > H*W:
            break
        # print(x,y)
        #tmp = Ad[y]-Ad[y-D]
        #S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        #tmp = Ad[y]-Ad[y-D]
        S = abs(Ad[y][0]-Ad[y-D][0])+abs(Ad[y][1]-Ad[y-D][1])

        # dp[x][y]=dp[x][y-D]+S
        d[y] = d[y-D]+S
        y += 1


# print(np.array(dp))

Q = int(input())
for i in range(Q):
    l, r = acinput()
    print(d[r]-d[l])


# print(Ad)
# print(np.array(dp))
print(d)

Submission status: Wrong Answer

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

H,W,D=acinput()
#Ad={}
Ad=[0]*(H*W+1)
for i in range(H):
    ar=acinput()
    for j,sar in enumerate(ar):
        Ad[sar]=np.array((i,j))

dp = [[0 for j in range(H*W+1)]for i in range(H*W+1)]

for x in range(1, H*W+1):
    dp[x][x]=0

for x in range(1,H*W+1):
    y=x+D
    while True:
        if y >= H*W:
            break
        #print(x,y)
        tmp = Ad[y]-Ad[y-D]
        S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        dp[x][y]=dp[x][y-D]+S
        y+=D
        

#print(np.array(dp))

Q=int(input())
for i in range(Q):
    l,r=acinput()
    print(dp[l][r])

Submission status: Wrong Answer

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

H,W,D=acinput()
Ad={}
for i in range(H):
    ar=acinput()
    for j,sar in enumerate(ar):
        Ad[sar]=np.array((i,j))

dp = [[-1 for j in range(H*W+1)]for i in range(H*W+1)]

for x in range(1, H*W+1):
    dp[x][x]=0

for x in range(1,H*W+1):
    y=x+D
    while True:
        if y >= H*W:
            break
        #print(x,y)
        tmp = Ad[y]-Ad[y-D]
        S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        dp[x][y]=dp[x][y-D]+S
        y+=D
        

#print(np.array(dp))

Q=int(input())
for i in range(Q):
    l,r=acinput()
    print(dp[l][r])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    H, W, D = Scanner.map_int()
    A = Scanner.int_list_list(H)
    Q = Scanner.int()
    query = Scanner.int_list_list(Q)
    M = [0] * (H*W + 1)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = (w, h)
    S = [0] * (H * W + 1)
    for i in reversed(range(1, H*W+1)):
        if i + D >= H*W+1:
            S[i] = 0
        else:
            S[i] = S[i+D] + abs(M[i][0] - M[i+D][0]) + abs(M[i][1] - M[i+D][1])
    print(S)
    for q in query:
        print(S[q[0]] - S[q[1]])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
h, w, d = list(map(int, input().split()))
grid = []
num = [[] for i in range(h*w+1)]
for i in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    for j in range(w):
        num[grid[i][j]]=[j+1, i+1]
k = math.ceil((h*w+1) / d)
#initialize
cost = [[0 for i in range(k)] for j in range(d)]
for i in range(d + 1,h*w+1):
    x, y = num[i]
    prex, prey = num[i - d]
    cost[i % d][i//d] = abs(prex - x) + abs(prey - y)
    cost[i % d][i//d] += cost[i % d][(i - d)// d]
print(cost) 
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r%d][r//d] - cost[l%d][l//d])

Submission status: Wrong Answer

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, D = lr()
A = [lr() for _ in range(H)]
Q = ir()
grid = [None] * (H*W + 1) # 1-indexed
for i in range(H):
    for j in range(W):
        grid[A[i][j]] = (i, j)

next_D = [0] * (H*W + 1)
for i in range(1, H*W + 1 - D):
    next_D[i] = abs(grid[i+D][0] - grid[i][0]) + abs(grid[i+D][1] - grid[i][1])

jump = [[0] * (H*W + 1) for i in range(H*W + 1)]
for i in range(1, H*W + 1 - D):
    for j in range(i+D, H*W + 1 - D, D):
        jump[i][j] = next_D[j-D]
        if j-D > i:
            jump[i][j] += jump[i][j-D]

#print(next_D)
#print(jump)
for i in range(Q):
    l, r = lr()
    answer = jump[l][r]
    print(answer)

# 49