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: Time Limit Exceeded

Solution code:
import numpy as np

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

for i in range(h):
    arr[i] = list(map(int, input().split()))

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

for i in range(q):
    lr[i] = list(map(int, input().split()))

ans = []
for l, r in lr:
    score = 0
    while l != r:
        tmp = l + d
        u = np.where(arr == l)
        v = np.where(arr == tmp)
        score += (abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0]))
        l += d
    ans.append(score)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

def mp(a,b):
    if a==b:
        return 0
    else:
        ah,aw=pos[a]
        bh,bw=pos[b]
        ret=abs(ah-bh)+abs(aw-bw)
        return ret

dis=[[0]*H*W for _ in range(H*W)]
def rec(a,b):
    if a==b:
        return 0
    if dis[a-1][b-1]!=0:
        return dis[a-1][b-1]
    else:
        if dis[b-1-D][b-1]!=0:
            return rec(a,b-D)+mp(b-D,b)
        else:
            return mp(a,a+D)+rec(a+D,b)



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=rec(L,R)
    print(ans)

Submission status: Time Limit Exceeded

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

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    nowh,noww=pos[L]
    now=L
    ans=0
    while now<R:
        newh,neww=pos[now+D]
        ans+=abs(nowh-newh)+abs(noww-neww)
        now+=D
        nowh=newh
        noww=neww
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np
# from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
N = H*W
ind = [0]*N
d = {}

A = []
for _ in range(H):
    row = list(map(int,readline().split()))
    A += row
    
for i in range(1,N+1):
    ind = A.index(i)
    x = ind // W
    y = ind % W
    d[i] = (x+1,y+1)
# print(d)

data = [[] for i in range(D)]
ac_data = []
for i in range(1,D+1):
    n = 1
    while i + D*n <= N: 
        x,y = d[i+D*(n-1)]
        nx,ny = d[i+D*n]
        power = abs(x-nx) + abs(y-ny)
        data[i%D].append(power)
        n += 1
# print(data)      
for row in data:
    row = [0] +row
    # ac_row = list(accumulate(row))
    ac_row = np.cumsum(row)
    ac_data.append(ac_row)

# print(ac_data)
Q = int(readline())
for i in range(Q):
    L,R = map(int,readline().split())
    k = L % D
    l = L // D 
    m = (R-L) // D
    if k == 0:
        print(ac_data[k][l-1+m]-ac_data[k][l-1])
    else:
        print(ac_data[k][l+m]-ac_data[k][l])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
N = H*W
ind = [0]*N
d = {}

A = []
for _ in range(H):
    row = list(map(int,readline().split()))
    A += row
    
for i in range(1,N+1):
    ind = A.index(i)
    x = ind // W
    y = ind % W
    d[i] = (x+1,y+1)
# print(d)

data = [[] for i in range(D)]
ac_data = []
for i in range(1,D+1):
    n = 1
    while i + D*n <= N: 
        x,y = d[i+D*(n-1)]
        nx,ny = d[i+D*n]
        power = abs(x-nx) + abs(y-ny)
        data[i%D].append(power)
        n += 1
# print(data)      
for row in data:
    row = [0] +row
    ac_row = list(accumulate(row))
    ac_data.append(ac_row)

# print(ac_data)
Q = int(readline())
for i in range(Q):
    L,R = map(int,readline().split())
    k = L % D
    l = L // D 
    m = (R-L) // D
    if k == 0:
        print(ac_data[k][l-1+m]-ac_data[k][l-1])
    else:
        print(ac_data[k][l+m]-ac_data[k][l])

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for h in range(H):
    grid[h] = list(map(int, input().split()))
number_yx = [[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x in range(W):
        number_yx[grid[y][x]] = [y,x]
fromto_cost = [[0]*(1+H*W) for _ in range(1+H*W)]
for mod_group in range(D):
    # 剰余ごとにスタートを決定
    start = mod_group+1
    previous = start
    fromto_cost[start][start] = 0
    previous_y, previous_x = number_yx[previous]
    cost = 0
    while previous+D <= (H*W):
        Next = previous+D 
        Next_y, Next_x = number_yx[Next]
        cost += abs(Next_y-previous_y) + abs(Next_x-previous_x)
        fromto_cost[start][Next] = cost

        previous = Next
        previous_y,previous_x = Next_y,Next_x

Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
    start, goal = map(int,input().split())
    mod = start % D
    base = mod
    if base == 0:
        base = D 
    base_to_goal = fromto_cost[base][goal]
    base_to_start = fromto_cost[base][start]
    ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

dist=[0]*(h*w-d)

for i in range(h*w-d):
  dist[i]+=abs(dict[i+d+1][0]-dict[i+1][0])+abs(dict[i+d+1][1]-dict[i+1][1])


ans=0

q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r,d):
      ans+=dist[j-1]

    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

dist=[0]*(h*w-d)

for i in range(h*w-d):
  dist[i]+=abs(dict[i+d+1][0]-dict[i+1][0])+abs(dict[i+d+1][1]-dict[i+1][1])


ans=0

q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    while True:
      if l==r:
        break
      ans+=dist[l-1]
      l+=d

    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))


ans=0

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    now=dict[l]
    while True:
      if l==r:
        break
      l+=d
      ans+=abs(now[0]-dict[l][0])+abs(now[1]-dict[l][1])
      now=dict[l]
    
    print(ans)
    ans=0

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range(H*W)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][(L1[j]-L1[j]%D)//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]-1-L1[j]%D)//D]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=(A-c)//D
  b=(B-c)//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  s,k=L[A-1]
  ans=0
  for j in range((B-A)//D):
    A+=D
    a,b=L[A-1]
    ans+=abs(a-s)+abs(b-k)
    s,k=a,b
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  s,k=L[A-1]
  ans=0
  for j in range((B-A)//D):
    a,b=L[A-1+(j+1)*D]
    ans+=abs(a-s)+abs(b-k)
    s=a
    k=b
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W,D=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR=[list(map(int,input().split())) for i in range(Q)]


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

dict_dir = {}

for i in range(Q):
    L = LR[i][0]
    R = LR[i][1]
    useMP = 0
    if (L,R) not in dict_dir:
        point = range(L,R+1,D)
        for p in range(1,len(point)):
            x0,y0 = dict_map[point[p-1]]
            x1,y1 = dict_map[point[p]]
            useMP += abs(x0-x1)+abs(y0-y1)
        dict_dir[(L,R)]=useMP
    else:
        useMP = dict_dir[(L,R)]
    print(useMP)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W,D=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR=[list(map(int,input().split())) for i in range(Q)]

dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)
        
for i in range(Q):
    useMP = 0
    point = range(LR[i][0],LR[i][1]+1,D)
    for p in range(1,len(point)):
        x0,y0 = dict_map[point[p-1]]
        x1,y1 = dict_map[point[p]]
        useMP += abs(x0-x1)+abs(y0-y1)
    print(useMP)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)

# Dで分類した累積和
# S[initial % D][j], n = r + D*j
S = [[0 for _ in range(H*W//D+D)] for _ in range(D)]
for i in range(D):
    for j in range(H*W // D):
        if i == 0 and j == 0:
            continue
        if i + (j+1)*D > H*W:
            break

        x, y = num[i + (j+1)*D]
        a, b = num[i + j*D]
        S[i][j+1] = S[i][j] + abs(x - a) + abs(y - b)
# print(S)
Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[r][R // D] - S[r][L // D])

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
H, W, D = I[:3]
A = I[3:3 + H * W]
Q = I[3 + H * W]
LR = I[4 + H * W:]

a_i = {a:i for i,a in enumerate(A)}


def calc(a1):
    a2 = a1 + D
    hw1 = a_i[a1]
    h1, w1 = divmod(hw1, W)
    hw2 = a_i[a2]
    h2, w2 = divmod(hw2, W)
    return abs(h2 - h1) + abs(w2 - w1)


score = [0] + [calc(i) for i in range(1, H * W + 1 - D)]
ans = []
for l, r in zip(LR[::2], LR[1::2]):
    ans += [sum(score[i] for i in range(l, r, D))]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)

    csum = [0] * (H * W + 1)
    for i in range(1, H * W + 1):
        N = (H * W - i) // D + 1
        csum[i] = [0] * N
        for j in range(N - 1):
            csum[i][j + 1] = (
                csum[i][j]
                + abs(vec[i + (j + 1) * D][0] - vec[i + j * D][0])
                + abs(vec[i + (j + 1) * D][1] - vec[i + j * D][1])
            )

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        ans[i] = csum[l][(r - l) // D]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        res = 0
        for j in range(l, r, D):
            res += abs(vec[j + D][0] - vec[j][0]) + abs(vec[j + D][1] - vec[j][1])
        ans[i] = res

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

B = []
for i in range(H):
  for j in range(W):
    B.append((A[i][j],(i,j)))

B = sorted(B)

for q in range(Q):
  l, r = lr[q]
  if l==r:
    print(0)
    continue
  ans = 0
  for i in range(l,r+D,D):
    idx = i-1
    if i == l:
      old = B[idx][1]
      continue
    new = B[idx][1]
    diff = abs(new[0] - old[0]) + abs(new[1] - old[1])
    ans += diff
    old = new
  print(ans)

Submission status: Time Limit Exceeded

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

B = []
for i in range(H):
  for j in range(W):
    B.append((A[i][j],(i,j)))

B = sorted(B)

for q in range(Q):
  l, r = lr[q]
  if l==r:
    print(0)
    continue
  ans = 0
  for i in range(l,r+D,D):
    idx = i-1
    if i == l:
      old = B[idx][1]
      continue
    new = B[idx][1]
    diff = abs(new[0] - old[0]) + abs(new[1] - old[1])
    ans += diff
    old = new
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import lru_cache
    h, w, d = map(int, input().split())

    a = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a.append((k, (i, j)))

    a.sort(key=lambda x: x[0])

    q = int(input())

    @lru_cache(maxsize=q)
    def Q(l, r):
        _, (x, y) = a[l - 1]

        s = 0
        for k, (i, j) in a[l - 1::d]:
            s += abs(x - i) + abs(y - j)
            if r == k:
                break
            x, y = i, j
        return s

    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        s = Q(l, r)
        res.append(s)

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = [int(x) for x in input().strip().split()]
    M = [0] * H
    C = {}
    revM = {}
    for h in range(H):
        M[h] = [int(x) for x in input().strip().split()]
        for i, w in enumerate(M[h]):
            revM[w] = (h, i)
    Q = int(input())
    for q in range(Q):
        ans = 0
        l, r = [int(x) for x in input().strip().split()]
        while l != r:
            # print('d={}, revM[l]={}'.format(d, revM[l]))
            if (l, r) not in C:
                C[(l, r)] = abs(revM[l][0] - revM[l+D][0]) + abs(revM[l][1] - revM[l+D][1])
                ans += C[(l, r)]
            else:
                ans += C[(l, r)]
            l += D
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i] = abs(x - w) + abs(y - h)

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[l:r:D].sum()


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i] = abs(x - w) + abs(y - h)

    for i in range(Q):
        l, r = LR[i]
        q = (r - l) // D
        for k in range(q):
            ans[i] += mp[l + D * k]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def dfs(H, W, D, A, mp):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i][i + D] = abs(x - w) + abs(y - h)

    for i in range(1, H * W + 1 - 2 * D):
        for j in range(i + 2 * D, H * W + 1):
            mp[i][j] = mp[i][j - D] + mp[j - D][j]


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    mp = [[0] * (H * W + 1) for _ in range(H * W + 1)]
    dfs(H, W, D, A, mp)

    ans = [mp[l][r] for l, r in zip(L, R)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [[0]*(h*w+1) for _ in range(d)]
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[i-1][j] = cost + roots[i-1][j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[(l-1)%d][r] - roots[(l-1)%d][l])

Submission status: Time Limit Exceeded

Solution code:
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 = [a.index(i) for i in range(n)]
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])

Submission status: Time Limit Exceeded

Solution code:
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 = [a.index(i) for i in range(n)]
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])

Submission status: Time Limit Exceeded

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

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

idx_list = [a.index(i) for i in range(n)]
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])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))

H, W, D = next(inp), next(inp), next(inp)
addr = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        v = next(inp)
        addr[v] = (i, j)

Q = next(inp)
for _ in range(Q):
    s, t = next(inp), next(inp)
    r, c = addr[s]
    cost = 0
    while s < t:
        s += D
        nr, nc = addr[s]
        cost += abs(nr - r) + abs(nc - c)
        r, c = nr, nc
    print(cost)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10000000)
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[[-1]*(H*W+1) for _ in range(H*W+1)]

for i in range(H*W+1):
    c[i][i]=0

def rec(a,b):
    if c[a][b]!=-1:
        return c[a][b]
    y,x=dic[a]
    ny,nx=dic[a+D]
    ret=abs(y-ny)+abs(x-nx)+rec(a+D,b)
    c[a][b]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    ans=rec(L,R)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)

def rec(n):
    if c[n]!=-1:
        return c[n]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

for i in range(Q):
    L,R=map(int,input().split())
    y,x=dic[L]
    ans=0
    while A[y][x]!=R:
        ny,nx=dic[A[y][x]+D]
        ans+=abs(y-ny)+abs(x-nx)
        y=ny
        x=nx
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    h, w, d = map(int, input().split())

    g = [list(map(int, input().split())) for _ in range(h)]

    M = 0
    for i in range(h):
        for j in g[i]:
            M = max(M, j)
    l = [0]*(M+1)
    ltup = [0]*(M+1)
    
    @lru_cache(maxsize=None)
    def main(num):
        for i in range(h):
            for j in range(w):
                if g[i][j] == num:
                    if num <= M-d:
                        l[num] = l[num+d]+abs(ltup[num+d][0]-i)+abs(ltup[num+d][1]-j)
                    ltup[num] = (i, j)
                    num -= d
                    if num >= 0:
                        main(num)
                    else:
                        return False
    for i in range(d):
        main(M-i)
    
    q=int(input())
    for i in range(q):
        lc,rc=map(int,input().split())
        print(l[lc]-l[rc])



resolve()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    h, w, d = map(int, input().split())

    g = [list(map(int, input().split())) for _ in range(h)]

    M = 0
    for i in range(h):
        for j in g[i]:
            M = max(M, j)
    l = [0]*(M+1)
    ltup = [0]*(M+1)
    
    @lru_cache(maxsize=None)
    def main(num):
        for i in range(h):
            for j in range(w):
                if g[i][j] == num:
                    if num <= M-d:
                        l[num] = l[num+d]+abs(ltup[num+d][0]-i)+abs(ltup[num+d][1]-j)
                    ltup[num] = (i, j)
                    num -= d
                    if num >= 0:
                        main(num)
                    else:
                        return False
    for i in range(d):
        main(M-i)
    
    q=int(input())
    for i in range(q):
        lc,rc=map(int,input().split())
        print(l[lc]-l[rc])



resolve()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit 
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    h, w, d = map(int, input().split())

    g = [list(map(int, input().split())) for _ in range(h)]

    M = 0
    for i in range(h):
        for j in g[i]:
            M = max(M, j)
    l = [0]*(M+1)
    ltup = [0]*(M+1)
    
    @jit
    def main(num):
        for i in range(h):
            for j in range(w):
                if g[i][j] == num:
                    if num <= M-d:
                        l[num] = l[num+d]+abs(ltup[num+d][0]-i)+abs(ltup[num+d][1]-j)
                    ltup[num] = (i, j)
                    num -= d
                    if num >= 0:
                        main(num)
                    else:
                        return False
    for i in range(d):
        main(M-i)
    
    q=int(input())
    for i in range(q):
        lc,rc=map(int,input().split())
        print(l[lc]-l[rc])



resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    h, w, d = map(int, input().split())

    g = [list(map(int, input().split())) for _ in range(h)]

    M = 0
    for i in range(h):
        for j in g[i]:
            M = max(M, j)
    l = [0]*(M+1)
    ltup = [0]*(M+1)

    def main(num):
        for i in range(h):
            for j in range(w):
                if g[i][j] == num:
                    if num <= M-d:
                        l[num] = l[num+d]+abs(ltup[num+d][0]-i)+abs(ltup[num+d][1]-j)
                    ltup[num] = (i, j)
                    num -= d
                    if num >= 0:
                        main(num)
                    else:
                        return False
    for i in range(d):
        main(M-i)
    
    q=int(input())
    for i in range(q):
        lc,rc=map(int,input().split())
        print(l[lc]-l[rc])



resolve()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc089/tasks/abc089_d

H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())
L=[0]*Q
R=[0]*Q
    
d=dict()
j=0
for b in A:
    for c in b:
        d[c]=j
        j +=1

for i in range(Q):
    L,R = map(int,input().split())
    ans = 0
    
    while L!=R: 
        tmp = d[L]
        p = tmp//W
        q = tmp %W
        L += D
        tmp2 = d[L]
        r = tmp2//W
        s = tmp2 %W
        #print(p,q,r,s)
        ans += abs(r-p) + abs(s-q)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]-1]=[i,j]
cost=[0 for i in range(w*h)]
for i in range(h*w):
    if i+d<h*w:
        cost[i]=abs(lis[i+d][0]-lis[i][0])+abs(lis[i+d][1]-lis[i][1])
#print(cost)
q=I()
for i in range(q):
    ans=0
    l,r=MI()
    for i in range(l,r,d):
        #print(i)
        ans+=cost[i-1]
    print(ans)