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())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(list(map(int, input().split()))):
        mass[a] += [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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, dtype=int)
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+1, num+1):
    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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
h,w,d = map(int,input().split())
ans = 0
x = [0]*(h*w+1)
y = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        x[a[j]] = j
        y[a[j]] = i
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for i in range((r-l)//d): 
        ans += abs(x[l+d*i]-x[l+d*(i+1)])+abs(y[l+d*i]-y[l+d*(i+1)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
h,w,d = map(int,input().split())
ans = 0
x = [0]*(h*w+1)
y = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        x[a[j]] = j
        y[a[j]] = i
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for i in range((r-l)//d): 
        ans += abs(x[l+d*i]-x[l+d*(i+1)])+abs(y[l+d*i]-y[l+d*(i+1)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
    H,W,D = map(int,input().split())
    A = [None] * (H*W+1)
    for i in range(H):
        j = 1
        for x in input().split():
            A[int(x)] = (i+1,j)
            j += 1

    # クエリ
    Q = int(input())
    for _ in range(Q):
        ans = 0
        L, R = map(int,input().split())

        for i in range(L+D,R+1,D):
            ans += abs(A[i][0] - A[i-D][0])
            ans += abs(A[i][1] - A[i-D][1])
        
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
q = int(input())
l = [0]*q ;r = [0]*q
for i in range(q): l[i],r[i] = map(int,input().split())
dct = {}

for i in range(h):
    for j in range(w):
        dct[a[i][j]] = (i,j)
    
for i in range(q):
    ans = 0
    n = l[i]
    cx,cy = dct[n]
    while dct[n] != dct[r[i]]:
        n += d
        nx,ny = dct[n]
        ans += abs(nx-cx)+abs(ny-cy)
        cx,cy = nx,ny
    print(ans)

Submission status: Time Limit Exceeded

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]*(10**7)

#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]))
        #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+=D
        

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

Submission status: Time Limit Exceeded

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



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))
        Ad[sar] = (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]))
        #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
        y+=D
        

#print(np.array(dp))

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


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

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
l = [list(map(int,input().split())) for i in range(h)]
ans = [[0]*(h*w+1) for i in range(d)]
px = [0]*(h*w+1)
py = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        px[l[i][j]],py[l[i][j]] = i,j  

count =[0]*(h*w+1)
for i in range(d+1,h*w+1):
    count[i] = count[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d])

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])

Submission status: Time Limit Exceeded

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

for i in range(h):
    for j in range(w):
        ans[l[i][j]%d][l[i][j]//d] = (l[i][j],i,j)

count =[0]*(h*w+1)
for i in range(2,len(ans[0])):
    if ans[0][i] == 0:
        break
    count[ans[0][i][0]] = count[ans[0][i-1][0]] + abs(ans[0][i][1]-ans[0][i-1][1])+abs(ans[0][i][2]-ans[0][i-1][2])
for i in range(1,d):
    for j in range(1,len(ans[i])):
        if ans[i][j] == 0:
            break
        count[ans[i][j][0]] = count[ans[i][j-1][0]] + abs(ans[i][j][1]-ans[i][j-1][1])+abs(ans[i][j][2]-ans[i][j-1][2])

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])

Submission status: Time Limit Exceeded

Solution code:
def solve(h, w, d, AA, q, LR):
    Ainv = {
        AA[y][x]: (x, y)
        for x in range(w)
        for y in range(h)
    }

    costs = [0] * q
    for i, (l, r) in enumerate(LR):
        while l != r:
            xf, yf = Ainv[l]
            xt, yt = Ainv[l + d]
            costs[i] += abs(xt - xf) + abs(yt - yf)
            l = AA[yt][xt]

    return costs

_h, _w, _d = map(int, input().split())
_AA = [list(map(int, input().split())) for _ in range(_h)]
_q = int(input())
_LR = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_h, _w, _d, _AA, _q, _LR), sep='\n')

Submission status: Time Limit Exceeded

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

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

# 49

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w,d = inpm()
    a = inpll(h)
    MAP = [0 for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            MAP[a[i][j]-1] = (i,j)
    cnt = [-1 for _ in range(h*w-d)]
    q = inp()
    for _ in range(q):
        l,r = inpm()
        ans = 0
        for i in range(l-1,r-d,d):
            x = i
            if cnt[x] == -1:
                X = MAP[i]
                Y = MAP[i+d]
                cost = abs(X[0]-Y[0]) + abs(X[1]-Y[1])
                cnt[x] = cost
            ans += cnt[i]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w,d = inpm()
    a = inpll(h)
    MAP = [0 for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            MAP[a[i][j]-1] = (i,j)
    cnt = []
    for i in range(h*w-d):
        x = MAP[i]
        y = MAP[i+d]
        cost = abs(x[0]-y[0]) + abs(x[1]-y[1])
        cnt.append(cost)
    q = inp()
    for _ in range(q):
        l,r = inpm()
        ans = 0
        for i in range(l-1,r-d,d):
            ans += cnt[i]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
Q = [list(map(int, input().split())) for _ in range(Q)]
# print(status)
for s, t in Q:
    ans = 0
    while s != t:
        tmp_t = s+D
        ans += abs((status[tmp_t][0] - status[s][0])) + abs(status[tmp_t][1]-status[s][1])
        s = tmp_t
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]

for i in range(h * w-d):
    num[i%d][i//d] = abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(sum(num[now % d - 1][(now - now % d) // d-1:(goal - now % d) // d-1]))
    else:
        print(sum(num[now%d-1][(now-now%d)//d:(goal-now%d)//d]))

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)]
lis = [[0,0] for i in range(h * w)]
for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]
q = int(input())
for _ in range(q):
    ans = 0
    now,want = map(int,input().split())
    now-=1
    want-=1
    while now != want:
        ans += abs(lis[now][0]-lis[now+d][0])+abs(lis[now][1]-lis[now+d][1])
        now += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = list(map(int,input().split()))
mat = [0 for i in range(H*W)]
A = []
for h in range(H):
    a = list(map(int,input().split()))
    A.append(a)
    for w in range(W):
        mat[a[w]-1] = [h,w]
Q = int(input())
LR = [list(map(int,input().split())) for i in range(Q)]

for l,r in LR:
    dis = 0
    now = mat[l-1]
    for i in range(l-1,r,D):
        dis += abs(mat[i][0]-now[0])+abs(mat[i][1]-now[1])
        now = mat[i]
    print(dis)

Submission status: Time Limit Exceeded

Solution code:
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)]
mat = [0 for i in range(H*W)]
for h in range(H):
    for w in range(W):
        mat[A[h][w]-1] = [h,w]
for l,r in LR:
    dis = 0
    now = mat[l-1]
    for i in range(l-1,r,D):
        dis += abs(mat[i][0]-now[0])+abs(mat[i][1]-now[1])
        now = mat[i]
    print(dis)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W,D = map(int,input().split())
MP = [None]*(H*W)
for h in range(H):
  X = list(map(int,input().split()))
  for w in range(W):
    MP[X[w]-1]=[h+1,w+1]
Q = int(input())
for h in range(Q):
  L,R = map(int,input().split())
  ans = 0
  for l in range(L,R,D):
    lD = l+D
    ans += abs(MP[lD-1][0]-MP[l-1][0])+abs(MP[lD-1][1]-MP[l-1][1])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = [None]*(H*W+1)
for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        A[v] = (i+1, j+1)

Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]
for l, r in LR:
    ans = 0
    while l < r:
        ans += abs(A[l][0]-A[l+D][0])+abs(A[l][1]-A[l+D][1])
        l += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W, D = MAP()
grid = build_grid(H, W, 0, int)
HW = {}
for i in range(H):
    for j in range(W):
        HW[grid[i][j]-1] = (i, j)

# nxt[k][i] := iからスタートして、2^k回移動した後にいる位置
nxt = list2d(17, H*W, -1)
# cost[k][i] := iからスタートして、2^k回移動した時にかかるコスト
cost = list2d(17, H*W, INF)
for h in range(H):
    for w in range(W):
        cur = grid[h][w] - 1
        if cur + D < H * W:
            h2, w2 = HW[cur+D]
            # 1つ先の移動先とコストを記録
            nxt[0][cur] = cur + D
            cost[0][cur] = abs(h-h2) + abs(w-w2)

# ダブリングのテーブル構築
for k in range(1, 17):
    for i in range(H*W):
        if nxt[k-1][i] == -1:
            continue
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]
        cost[k][i] = cost[k-1][i] + cost[k-1][nxt[k-1][i]]

for i in range(INT()):
    l, r = MAP()
    l -= 1; r -= 1
    cnt = (r - l) // D
    cur = l
    ans = 0
    # cnt回先に進む時のコストを確認
    for k in range(16, -1, -1):
        if cnt & 1<<k:
            ans += cost[k][cur]
            cur = nxt[k][cur]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W , D = map(int, input().split())
fields = []
X = []
for i in range(H):
    # fields.append(list(map(int, input().split())))
    X.extend(list(map(int, input().split())))
pairs = [(x-1,i) for i,x in enumerate(X)]
pairs.sort()
# print(pairs)
def calc_dist(a,b):
    return abs(a//W-b//W) + abs(a%W-b%W)

Q = int(input())
for i in range(Q):
    L1,R1 = map(int, input().split())
    ans = 0
    for i in range(L1,R1,D):
        a = pairs[i-1][1]
        b = pairs[i+D-1][1]
        ans += calc_dist(a,b)
        # print(i,a,b,ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    Q = int(input())
    r = 0
    cache = {}
    for _ in range(Q):
        l, r = map(int, input().split())
        if (l, r) not in cache:
            cache[(l, r)] = sum(C[l - 1:r - 1:D])
        print(cache[(l, r)])
        
main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W,D=MI()
    A=LLIN(H)
    
    def get_cost(fr:tuple, to:tuple):
        return abs(fr[0]-to[0]) + abs(fr[1]-to[1])

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

    cumsum = [[0]*(H*W+1+D) for _ in range(D)]
    for d in range(D):
        for x in range(1,H*W):
            if x+D not in cord_of_x:
                break
            cost = get_cost(cord_of_x[x], cord_of_x[x+D])
            cumsum[d][x+D]+=cumsum[d][x]+cost


    Q=I()
    LR=LLIN(Q)
    for l,r in LR:
        d = l%D
        print(cumsum[d][r]-cumsum[d][l])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W,D=MI()
    A=LLIN(H)
    
    def get_cost(fr:tuple, to:tuple):
        return abs(fr[0]-to[0]) + abs(fr[1]-to[1])

    cord_of_x = {}
    for h in range(H):
        for w in range(W):
            cord_of_x[A[h][w]] = (h,w)
    
    # ワーシャルフロイド
    def warshall_floyd(d, N):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j]=min(d[i][j], d[i][k] + d[k][j])
    
    N=H*W+1
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    for h in range(H):
        for w in range(W):
            if A[h][w]+D in cord_of_x:
                to = cord_of_x[A[h][w] + D]
                d[A[h][w]][A[h][w]+D] = get_cost((h,w), to)
    warshall_floyd(d, N)

    Q=I()
    LR=LLIN(Q)
    for l,r in LR:
        print(d[l][r])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
    Q = int(input())
    for q in range(Q):
        ans = 0
        le, ri = (int(i) for i in input().split())
        while le != ri:
            j, i = num_to_xy[le]
            y, x = num_to_xy[le + D]
            ans += abs(x - i) + abs(y - j)
            le += D
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

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

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

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

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i%D][i]=dpsum[i%D][i-D]+dp[i]
  else:
    dpsum[i%D][i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R%D][R-D]-dpsum[L%D][L-D])
  else:
    print(dpsum[R%D][R-D])

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

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

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  print(sum(dp[L:R:D]))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
X, Y = [-1] * H * W, [-1] * H * W

for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        X[A[w] - 1], Y[A[w] - 1] = h, w

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = 0
    while L != R:
        ans += abs(X[L - 1] - X[L + D - 1]) + abs(Y[L - 1] - Y[L + D - 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)]
x=[]

def find_element(k):
    global h,w
    for i in range(h):
        for j in range(w):
            if a[i][j]==k:
                return (i,j)

def make_distance(S,T):
    return abs(S[0]-T[0])+abs(S[1]-T[1])

for i in range(1,d+1):
    l=(h*w-i)//d
    x.append([0]*(l+1))
for i in range(1,d+1):
    l=len(x[i-1])
    for j in range(l-1):
        s=find_element(i+d*j)
        t=find_element(i+d*(j+1))
        x[i-1][j+1]=x[i-1][j]+make_distance(s,t)

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    p=l%d
    if p==0:
        v1=l//d-1
        v2=r//d-1
        print(x[d-1][v2]-x[d-1][v1])
    else:
        v1=l//d
        v2=r//d
        print(x[p-1][v2]-x[p-1][v1])
#print(x)

Submission status: Time Limit Exceeded

Solution code:

def main():
    h,w,d = map(int,input().split())
    dic = {}
    for y in range(h):
        line = list(map(int,input().split()))
        for x in range(w):
            num = line[x]
            dic[num] = (x,y)
    Q = int(input())
    for q in range(Q):
        l,r = map(int,input().split())
        cst = 0
        while l != r:
            (x,y) = dic[l]
            (nx,ny) = dic[l+d]
            cst += abs(nx - x) + abs(ny - y)
            l += d
        print(cst)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    cst = 0
    while l != r:
        (x,y) = dic[l]
        (nx,ny) = dic[l+d]
        cst += abs(nx - x) + abs(ny - y)
        l += d
    print(cst)