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:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    N = H*W

    ## ある数字の座標をO(1)で取得するため
    matrix = [()]*(N+1)
    for h in range(H):
        for w in range(W):
            matrix[A[h][w]] = (h,w)
    
    def get_distance(start: int, end: int) -> int:
        start_x = matrix[start][0]
        start_y = matrix[start][1]
        end_x = matrix[end][0]
        end_y = matrix[end][1]
        return abs(start_x-end_x)+abs(start_y-end_y)

    distance = [[0 for _ in range(N+1)] for _ in range(N+1)]

    for start in range(1,D+1):
        end = start
        prev_end = end

        while end <= N:
            distance[start][end] = distance[start][prev_end]+ get_distance(prev_end,end)
            prev_end = end
            end += D
    
    for i in range(Q):
        s = L[i]%D
        if s == 0:
            s = D
        d = distance[s][R[i]]-distance[s][L[i]]
        print(d)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]"
    R = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#89d
from functools import lru_cache
#再帰の限度を拡張
import sys
sys.setrecursionlimit(1000000)


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

value_coordinate_dict = {}

for i in range(1,H+1):
    A_list = [int(e) for e in input().split()]
    for j in range(1,W+1):
        value_coordinate_dict[A_list[j-1]] = (i,j) 

@lru_cache(maxsize=100000)
def calc_cmp(from_number,to_number): #cmp:消費comsumption 魔力magic power
    #print("###",from_number,"→",to_number)

    #終了条件
    if from_number == to_number:
        #print(from_number,"→",to_number,"= 0")
        return 0
    elif from_number + D == to_number:
        from_coordinate = value_coordinate_dict[from_number]
        to_coordinate = value_coordinate_dict[to_number]
        cmp = abs(to_coordinate[0] - from_coordinate[0]) + abs(to_coordinate[1] - from_coordinate[1])
        #print(from_number,"→",to_number,"=",cmp)
        return cmp
    #継続
    else:
        next_number = from_number + D
        return calc_cmp(next_number,to_number) + calc_cmp(from_number,next_number)        
            
Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
#89d
from functools import lru_cache
#再帰の限度を拡張
import sys
sys.setrecursionlimit(1000000)


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

value_coordinate_dict = {}

for i in range(1,H+1):
    A_list = [str(e) for e in input().split()]
    for j in range(1,W+1):
        value_coordinate_dict[int(A_list[j-1])] = (i,j) 

@lru_cache(maxsize=100000)
def calc_cmp(from_number,to_number): #cmp:消費comsumption 魔力magic power
    #print("###",from_number,"→",to_number)

    #終了条件
    if from_number == to_number:
        #print(from_number,"→",to_number,"= 0")
        return 0
    elif from_number + D == to_number:
        from_coordinate = value_coordinate_dict[from_number]
        to_coordinate = value_coordinate_dict[to_number]
        cmp = abs(to_coordinate[0] - from_coordinate[0]) + abs(to_coordinate[1] - from_coordinate[1])
        #print(from_number,"→",to_number,"=",cmp)
        return cmp
    #継続
    else:
        next_number = from_number + D
        return calc_cmp(next_number,to_number) + calc_cmp(from_number,next_number)        
            
Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def search(start, goal, arr, save,  D):
    mp = 0
    tmp = start
    ind = np.argwhere(arr == start)
    x, y = ind[0][0], ind[0][1]
    if save[x][y] != 0:
        return save[x][y]

    else:
        sx, sy = x, y
        while tmp != goal:
            tmp += D
            tmp_ind = np.argwhere(arr == tmp)
            i, j = tmp_ind[0][0], tmp_ind[0][1]
            mp += abs(x - i) + abs(y - j)
            x, y = i, j

        save[sx][sy] = mp

        return mp


H, W, D = map(int, input().split())
num_li = []
pro_li = []
ans = 0
save = [[0 for _ in range(W)] for i in range(H)]

for _ in range(H):
    tmp = list(map(int, input().split()))
    num_li.append(tmp)

num_arr = np.array(num_li)

Q = int(input())
for _ in range(Q):
    tmp1, tmp2 = map(int, input().split())
    pro_li.append([tmp1, tmp2])

for i in pro_li:
    print(search(i[0], i[1], num_arr, save, D))

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

number_list = [[] for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

for l, r in LR:
    cnt = 0
    while l != r:
        x, y = number_list[l]
        l += D
        nx, ny = number_list[l]
        cnt += (abs(x-nx) + abs(ny - y))
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
import collections
table=collections.defaultdict(tuple)

field=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
  for j in range(W):
    table[field[i][j]]=(i,j)
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
  ans=0
  x = table[LR[i][0]]
  value=LR[i][0]
  now=list(x)
  while(value != LR[i][1]):
    value+=D
    next=table[value]
    ans+=abs(next[0]-now[0])+abs(next[1]-now[1])
    now[0],now[1]=next[0],next[1]
    
  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)]

li = [[]] * (H * W)
for i in range(H):
  for j in range(W):
    li[A[i][j] - 1] = [j, i]

cost = [[0 for _ in range(H * W)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 

# print(cost)

for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
cell = {}
for i in range(h):
  row = list(map(int, input().split()))
  for j, a in enumerate(row):
    cell[a] = (i, j)
max_point = h * w
req_mp = [-1 for _ in range(max_point)]

q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  result = 0
  p = l
  while p < r:
    if req_mp[p] == -1:
      magic = abs(cell[p+d][0] - cell[p][0]) + abs(cell[p+d][1] - cell[p][1])
      req_mp[p] = magic
    result += req_mp[p]
    p += d
  print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    for _ in range(q):
        l, r = map(int1, input().split())
        ans = 0
        i0, j0 = atoij[l]
        while l < r:
            l += d
            i1, j1 = atoij[l]
            ans += abs(i0 - i1) + abs(j0 - j1)
            i0, j0 = i1, j1
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
def dijkstra(start, node_num, cost):
    '''
    start:始点
    node_num:ノード数
    cost: cost[u][v]がuからvへの重みとなるような配列
    -------------------------------------------
    dist: i番目が始点から頂点iまでの最短距離になる配列
    '''
    dist = [float('inf')] * node_num
    used = [False] * node_num
    dist[start] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(node_num):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and dist[i] < dist[v]:
                v = i

        ### 全ての頂点が使われてた場合は終了
        if v == -1:
            break
        ### 探してきた頂点を使って距離の更新
        used[v] = True
        for i in range(node_num):
            dist[i] = min(dist[i], dist[v] + cost[v][i])
        
    return dist

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

cost = [[float('inf') for _ in range(h*w)] for _ in range(h*w)]
for hi in range(h):
    for wi in range(w):
        nodenum = field[hi, wi] - 1
        for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if (0 <= hi+dh <= h-1) and (0<= wi+dw <= w-1):
                cost[nodenum][field[hi+dh, wi+dw]-1] = 1
dijk = []
for i in range(h*w):
    dijk.append(dijkstra(start=i, node_num=h*w, cost=cost))

def search(dijk, l, r, d):
    mana = 0
    while l < r:
        mana += dijk[l-1][l+d-1]
        l += d
    print(mana)

question = int(input())
for _ in range(question):
    l, r = map(int, input().split())
    search(dijk=dijk, l=l, r=r, d=d)

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
h, w, d = map(int, input().split())
field = []
for _ in range(h):
    wi = list(map(int, input().split()))
    field.append(wi)
field = np.array(field)
 
def search(field, l, r, d):
    mana = 0
    while l < r:
        mae = np.where(field==l)
        i, j = mae[0][0], mae[1][0]
        ushiro = np.where(field==l+d)
        x, y = ushiro[0][0], ushiro[1][0]
        mana += abs(x-i) + abs(y-j)
        
        l += d
    print(mana)
question = int(input())
for _ in range(question):
    l, r = map(int, input().split())
    search(field=field, l=l, r=r, d=d)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W, D = map(int, input().split())
    A = []
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        A.append(a)
        for i, x in enumerate(a):
            d[x-1] = h*W + i
    Q = int(input())
    for q in range(Q):
        ans = 0
        l, r = map(int, input().split())
        while l != r:
            ans += abs(d[l-1]//W - d[l+D-1]//W) + abs(d[l-1]%W - d[l+D-1]%W)
            l += D
        print(ans)


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

dx = [0 for _ in range(h*w+5)]
dy = [0 for _ in range(h*w+5)]

for i in range(h):
    for j in range(w):
        dx[a[i][j]] = i
        dy[a[i][j]] = j

dfromd = [0 for _ in range(h*w+5)]

for i in range(h*w-d+3):
    dfromd[i] = abs(dx[i+d]-dx[i])+abs(dy[i+d]-dy[i])

q = int(input())
for _ in range(q):
    l,r=map(int,input().split())
    res = 0
    while l < r:
        res += dfromd[l]
        l += d
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#%%
h, w, d = map(int, input().split())
a = [0] * h
for i in range(h):
    a[i] = list(map(int, input().split()))
q = int(input())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

pos = [[0] for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = [i+1, j+1]
#print(pos)

cost = [[0]*(h*w+1) for i in range(h*w+1)]
#print(cost)

for i in range(1, len(cost)):
    for j in range(i, len(cost)):
        pos1 = pos[i]
        pos2 = pos[j]
        dist = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
        cost[i][j] = dist

##print(np.array(cost))


for i in range(q):
    tmp = 0
    while l[i] != r[i]:
        tmp += cost[l[i]][l[i]+d]
        l[i] += d
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
#%%
h, w, d = map(int, input().split())
a = [0] * h
for i in range(h):
    a[i] = list(map(int, input().split()))
q = int(input())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

pos = [[0] for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = [i+1, j+1]
#print(pos)

cost = [[0]*(h*w+1) for i in range(h*w+1)]
#print(cost)

for i in range(1, len(cost)):
    for j in range(i, len(cost)):
        pos1 = pos[i]
        pos2 = pos[j]
        dist = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
        cost[i][j] = dist

import numpy as np
##print(np.array(cost))


for i in range(q):
    tmp = 0
    while l[i] != r[i]:
        tmp += cost[l[i]][l[i]+d]
        l[i] += d
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=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)]
data=[[0]*(h*w//d+1) for i in range(d)]
for i in range(h):
    for j in range(w):
        b=a[i][j]%d
        c=a[i][j]//d
        data[b][c]=[i, j]
for u in lr:
    l,r=u
    b=l%d
    c=l//d
    e=r//d
    ans=0
    for i in range(c,e):
        x,y=data[b][i]
        X,Y=data[b][i+1]
        ans+=abs(x-X)+abs(y-Y)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        bisect.insort_left(a_ls, (a[x], x, y))

#a_ls.sort(key=lambda x:x[0])
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    _sum = 0
    for ind in range(l, r, d):
        ind -= 1
        start = a_ls[ind]
        goal = a_ls[ind+d]
        _sum += abs(start[2] - goal[2]) + abs(start[1] - goal[1])
    print(_sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        a_ls += [(a[x], x, y)]

a_ls.sort(key=lambda x:x[0])
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    _sum = 0
    for ind in range(l, r, d):
        ind -= 1
        start = a_ls[ind]
        goal = a_ls[ind+d]
        _sum += abs(start[2] - goal[2]) + abs(start[1] - goal[1])
    print(_sum)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    while i <= h*w - d:
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5)
input = sys.stdin.readline

H, W, D = map(int, input().split())
pos = [0] * (H * W + 1)

for i in range(H):
    line = list(map(int, input().split()))
    for j, l in enumerate(line):
        pos[l] = (i, j)

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())

    ans = 0

    while L != R:
        dx = pos[L + D][0] - pos[L][0]
        dy = pos[L + D][1] - pos[L][1]
        ans += abs(dx) + abs(dy)
        L += D

    print(ans)

Submission status: Time Limit Exceeded

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

L = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        L[A[i][j]] = [i, j]
        
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    while l < r:
        ans += abs(L[l+D][0]-L[l][0])+abs(L[l+D][1]-L[l][1])
        l += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int,input().split())) for i in range(Q)]
P = [None]*(H*W)
for i in range(H):
    for j in range(W):
        P[A[i][j]-1] = [i,j]
for q in range(Q):
    mp = 0
    left = S[q][0]-1
    for d in range((S[q][1]-S[q][0])//D):
        mp += abs(P[left][0]-P[left+D][0])+abs(P[left][1]-P[left+D][1])
        left += D
    print(mp)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main() :
    H,W,D = map(int,input().split())
    Point = {}
    for y in range(H) :
        line = list(map(int,input().split()))
        for x,p in enumerate(line) :
            Point[p] = (y,x)

    Q = int(input())

    def dist(ny,nx,py,px) :
        return abs(ny-py) + abs(nx-px)

    for i in range(Q) :
        l,r = map(int,input().split())
        ny,nx = Point[l]
        res = 0
        while l != r :
            l += D
            py,px = ny,nx
            ny,nx = Point[l]
            res += dist(ny,nx,py,px)
        print(res)
main()

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
Point = {}
for y in range(H) :
    line = list(map(int,input().split()))
    for x,p in enumerate(line) :
        Point[p] = (y,x)

Q = int(input())

def dist(ny,nx,py,px) :
    return abs(ny-py) + abs(nx-px)

for i in range(Q) :
    l,r = map(int,input().split())
    ny,nx = Point[l]
    res = 0
    while l != r :
        l += D
        py,px = ny,nx
        ny,nx = Point[l]
        res += dist(ny,nx,py,px)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

H,W,D = 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)]

Point = {}
for y in range(H) :
    for x in range(W) :
        Point[A[y][x]] = (y, x)

def dist (y1,x1,y2,x2) :
    return abs(y1-y2) + abs(x1-x2)

for i in range(Q) :
    res = 0
    l,r = LR[i][0], LR[i][1]
    while l != r :
        l += D
        res += dist(Point[l][0], Point[l][1], Point[l-D][0], Point[l-D][1])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = 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)]

Point = {}
for y in range(H) :
    for x in range(W) :
        Point[A[y][x]] = (y, x)

def dist (y1,x1,y2,x2) :
    return abs(y1-y2) + abs(x1-x2)

for i in range(Q) :
    res = 0
    l,r = LR[i][0], LR[i][1]
    while l != r :
        l += D
        res += dist(Point[l][0], Point[l][1], Point[l-D][0], Point[l-D][1])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
Board = [0] * (H*W+1)
for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        Board[A[w]] = [w+1, h+1]

ansdict = dict()
for i in range(int(input())):
    L, R = map(int, input().split())
    if L*100000 + R in ansdict.keys():
        print(ansdict[L*100000 + R])
    else:
        ans = 0
        for j in range(L+D, R+1, D):
            ans += abs(Board[j][0] - Board[j-D][0]) + abs(Board[j][1] - Board[j-D][1])
        ansdict[L*100000 + R] = ans
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, D = map(int, input().split())

grid = [[] for h in range(H)]
for h in range(H):
    grid[h] = [int(_) for _ in input().split()]

np_grid = np.array(grid).ravel()


Q = int(input())
for q in range(Q):
    ans = 0
    L, R = map(int, input().split())
    if L == R:
        print(ans)
        continue
    else:
        while L != R:
            h_before = np.where(np_grid==L)[0][0] // 3
            w_before = np.where(np_grid==L)[0][0] % 3
            h_after = np.where(np_grid==(L+D))[0][0] // 3
            w_after = np.where(np_grid==(L+D))[0][0] % 3
            L += D
            ans += (abs(h_before - h_after) + abs(w_before - w_after))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
dp = [[0]*(H+1)*(W+1) for i in range(D)]
dic = {}
for i in range(H):
  a = [int(i) for i in input().split()]
  for j in range(W):
    # y, x
    dic[a[j]] = (i, j)

for i in range(D):
  ps = i
  if ps==0:
    ps = D
  count = 0
  y, x = dic[ps]
  while True:
    ps += D
    if H*W<ps:
      break
    count += 1
    ny, nx = dic[ps]
    dp[i][count] = dp[i][count-1]+abs(ny-y)+abs(nx-x)
    y = ny
    x = nx


Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  ID = L%D
  LI = L//D
  RI = R//D
  if ID!=0:
    print(dp[ID][RI]-dp[ID][LI])
  else:
    print(dp[ID][RI-1]-dp[ID][LI-1])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
mass = [0]*(H*W+1)
for y in range(1,H+1):
    for x,i in enumerate(input().split()):
        mass[int(i)]= (y,x+1)

Q = int(input())
for _ in range(Q):
    ans = 0
    L, R = map(int, input().split())
    while L < R:
        ans += abs(mass[L + D][0] - mass[L][0]) + abs(mass[L + D][1] - mass[L][1])
        L += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = [[int(j) for j in input().split()] for i in range(H)]
B = [(-1, -1) for j in range(H*W)]
for i in range(H):
    for j in range(W):
        B[A[i][j]-1] = (i, j)

C = [-1] * H*W
for i in range(H*W-D):
    fx, fy = B[i+D]
    tx, ty = B[i]
    C[i] = abs(fx-tx)+abs(fy-ty)

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = 0
    for i in range(L, R, D):
        ans += C[i-1]
    print(ans)

Submission status: Time Limit Exceeded

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

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

a2dist = [None]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i] = dist(a2pos[i+D], a2pos[i])
  

q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  print(sum(a2dist[l:r:D]))

Submission status: Time Limit Exceeded

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

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

a2dist = [None]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i] = dist(a2pos[i+D], a2pos[i])
  

q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  ans = 0
  now = l
  while now != r:
    ans += a2dist[now]
    now += D
  print(ans)

Submission status: Time Limit Exceeded

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

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  ans = 0
  now = l
  while now != r:
    ans += dist(a2pos[now+D], a2pos[now])
    now += D
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l1=[LI() for _ in range(h)]
  q=I()
  l2=[LI() for _ in range(q)]

  ans=[]
  for a,b in l2:
    _ans=0
    ff=True
    f1=f2=False
    _x=_y=0
    while True:
      for i,x in enumerate(l1):
        for j,y in enumerate(x):
          if a==y:
            if b==a:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              ans.append(_ans)
              f1=f2=True
              break
            else:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              _x=i
              _y=j
              a+=d
        if f1:
          break
      if f2:
        break

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l1=[LI() for _ in range(h)]
  q=I()
  l2=[LI() for _ in range(q)]

  ans=[]
  _x=_y=0
  for a,b in l2:
    _ans=0
    ff=True
    f1=f2=False
    while True:
      for i,x in enumerate(l1):
        for j,y in enumerate(x):
          if a==y:
            if b==a:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              ans.append(_ans)
              f1=f2=True
              break
            else:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              _x=i
              _y=j
              a+=d
        if f1:
          break
      if f2:
        break

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Time Limit Exceeded

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

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


for i in range(Q):
    L, R = map(int, input().split())
    ans = 0
    for x in range(L, R, D):
        ans += get_dist(x, x+D)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,d=map(int,input().split())
nums=[[0 for s in range(w)] for i in range(h)]
gya=[[0,0] for i in range(h*w)]
for i in range(h):
    nums[i]=list(map(int,input().split()))
    for j in range(w):
        gya[nums[i][j]-1]=[i,j]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    m=(r-l)//d
    ans=0
    for j in range(1,m+1):
        ans+=abs(gya[l+j*d-1][0]-gya[l+d*(j-1)-1][0])+abs(gya[l+j*d-1][1]-gya[l+d*(j-1)-1][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
nums=[[0 for s in range(w)] for i in range(h)]
gya=[[0,0] for i in range(h*w)]
for i in range(h):
    nums[i]=list(map(int,input().split()))
    for j in range(w):
        gya[nums[i][j]-1]=[i,j]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    m=(r-l)//d
    ans=0
    for j in range(1,m+1):
        ans+=abs(gya[l+j*d-1][0]-gya[l+d*(j-1)-1][0])+abs(gya[l+j*d-1][1]-gya[l+d*(j-1)-1][1])
    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());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=0
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

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());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=1
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)