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:
from sys import stdin
def input():
    return stdin.readline().strip()

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

    x = [0] * (h * w)
    y = x.copy()
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            x[a[j] - 1] = i
            y[a[j] - 1] = j

    ans = []
    q = int(input())
    for _ in range(q):
        # s = answer
        s = 0
        l, r = map(int, input().split())
        for i in range(l-1, r-1, d):
            s += abs(x[i] - x[i+d]) + abs(y[i] - y[i+d])
        ans.append(s)

    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

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

    ans = []
    q = int(input())
    for _ in range(q):
        # s = answer
        s = 0
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        for i in range(l, r, d):
            v, w = num[i]
            x, y = num[i+d]
            s += abs(v-x) + abs(w-y)
        ans.append(s)

    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

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

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

  Q=int(input())
  for q in range(Q):
    l,r=map(int,input().split())
    t,i=0,~-l  
    for j in range((r-l)//D):
      t+=abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D
    print(t)

main()

Submission status: Time Limit Exceeded

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

A=list()
for h in range(H):
  for w,a in enumerate(map(int,input().split())):
    A.append([a,h,w])

A=sorted(A, key=lambda x:x[0])

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  t,i=0,~-l  
  for j in range((r-l)//D):
    t+=abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
    i+=D
  print(t)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
adr = [-1]*(h*w) #indexの数字は[i,j]に書かれている
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        adr[a[j]-1] = [i,j]
q = int(input())

ans = []
for i in range(q):
    l,r = map(int,input().split())
    now = l-1
    cost = 0
    while now != r-1:
        cost += abs(adr[now][0]-adr[now+d][0])+abs(adr[now][1]-adr[now+d][1])
        now += d
    ans.append(cost)
    
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
l=[[] for t in range(h*w)]
for i in range(h):
  ll=list(map(int,input().split()))
  for j in range(w):
    l[ll[j]-1]=[i,j]
q=int(input())
f=lambda x:int(x)-1
for qq in range(q):
  ans=0
  a,b=map(f,input().split())
  for x in range(a,b+1-d,d):
    ans+=abs(l[x+d][0]-l[x][0])+abs(l[x+d][1]-l[x][1])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  X.append(_)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  if l>r:
    r+=N
  g=l%D
  ans=0
  for i in range(l,r,D):
    ans+=X[g][(i%N)//D]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  if l>r:
    r+=N
  l,r=l-1,r-1
  ans=0
  for i in range(l+D,r+1,D):
    ans+=sub(P[i%N],P[(i-D)%N])
  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())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + abs(p[j][0]-p[j-D][0]) + abs(p[j][1] - p[j-D][1]) 

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

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

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]] = (i, j)

d = [[float('inf')]*(H*W) for _ in range(H*W)]

for i in range(1, H*W+1):
    for j in range(1, H*W+1):
        dist = abs(p[i][0]-p[j][0]) + abs(p[i][1]-p[j][1])
        d[i-1][j-1] = dist
        d[j-1][i-1] = dist


dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + d[j][j-D]

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

Submission status: Time Limit Exceeded

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

A = [[] for _ in range(H)]
Aset = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,input().split()))
    Aset[i] = set(A[i])

#1,1+D,1+2D,...
#2,2+D,2+2D,...
#...
#D,2D,3D,...
cost = [0]*(H*W+1)
for i in range(1,D+1):
    num = i
    now = None#座標
    while True:
        if num > H*W:
            break
        for row in range(H):
            if num in Aset[row]:
                #print(row)
                ind = A[row].index(num)
                if now == None:
                    now = (ind, row)#x,y
                    cost[num] = 0
                else:
                    cost[num] = cost[num-D] + abs(ind-now[0]) + abs(row-now[1])
                    now = (ind, row)
        num += D

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h , w , d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
ans = [-1 for i in range(h*w + 1)]
for i in range(1,h*w+1):
    if ans[i] == -1:
        ans[i] = 0
        p = deque()
        flag = False
        for x in range(h):
            if flag:
                break
            for y in range(w):
                if a[x][y] == i:
                    p.append((i,x,y))
                    flag = True
                    break
        while p:
            now , nowx , nowy = p.popleft()
            flag = False
            if now + d > h*w:
                break
            for nexx in range(h):
                if flag:
                    break
                for nexy in range(w):
                    if a[nexx][nexy] == now + d:
                        p.append((now+d,nexx,nexy))
                        ans[now+d] = ans[now] + abs(nowx-nexx) + abs(nowy-nexy)
                        flag = True
                        break 

    else:
        continue

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

Submission status: Time Limit Exceeded

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

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

res = []
q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    ans = 0
    px, py = pos[l]
    for j in range(l, r+1, d):
        x, y = pos[j]
        ans += abs(px - x) + abs(py - y)
        px, py = pos[j]

    res.append(ans)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def myindex(l, element, default=-1):
    if element in set(l):
        return l.index(element)
    else:
        return default

def main():
    H, W, D = map(int, input().split())
    grid = []; locale = [0]*(H*W)
    for i in range(H):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            x, y = i+1, j+1
            locale[t-1] = (x, y)
        grid.append(tmp)
    
    power = []
    for k in range(H*W-D):
        fr = locale[k]
        to = locale[k+D]
        need = abs(fr[0]- to[0]) + abs(fr[1] - to[1])
        power.append(need)

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        d = (R - L)//D
        print(sum(power[(L-1)::D][:d]))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
l=[0]*(h*w)
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        l[a[j]-1]=(i,j)
q=int(input())
rng=[]
for i in range(q):
    L,R=map(int,input().split())
    L -= 1
    route=l[L:R:d]
    rng.append(route)

for i in rng:
    ans=0
    st=i[0]
    for j in range(1,len(i)):
        ne=i[j]
        ans += abs(st[0]-ne[0])+abs(st[1]-ne[1])
        st=ne
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
table=[0]*((((h*w)//d).bit_length())*h*w)
now=1
for i in range(1,h*w-d+1):
    a,s=ind[i]
    de,f=ind[i+d]
    table[i-1+d]=abs(a-de)+abs(s-f)
step=2
for i in range(1,((h*w)//d).bit_length()):
    for j in range(1,h*w-step*d+1):
        table[j-1+step*d+i*h*w]=table[j-1+d*step//2+(i-1)*h*w]+table[j-1+d*step+(i-1)*h*w]
    step*=2
#print(*[table[k*h*w:k*w*h+h*w]for k in range(((h*w)//d).bit_length())],sep="\n")
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    times=(r-l)//d
    cost=0
    now=1
    kata=0
    while times:
        if times%2:
            l+=d*now
            cost+=table[l-1+kata*h*w]

        times//=2
        now*=2
        kata+=1
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
dic = {}

for i in range(h):
    for j in range(w):
        dic[a[i][j]] = i,j
    
q = int(input())

for _ in range(q):
    l,r = map(int,input().split())
    point = 0
    for i in range(1,(r-l)//d+1):
        point += abs(dic[l+d*(i-1)][0]-dic[l+d*i][0])+abs(dic[l+d*(i-1)][1]-dic[l+d*i][1])
    print(point)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = []
for i in range(H):
  a = list(map(int, input().split()))
  for j in range(W):
    A.append([a[j],i,j])
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  j = 0
  while A[j][0] != L:
    j += 1
  l = j
  L += D
  oldl = l
  ans = 0
  while L <= R:
    k = 0
    while A[k][0] != L:
      k += 1
    l = k
    ans = ans + abs(A[oldl][1]-A[l][1])+abs(A[oldl][2]-A[l][2])
    L += D
    oldl = l
  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)]
nml = [None for _ in range(h*w)]
for i in range(h):
	for j in range(w):
		nml[a[i][j]-1] = (i, j)
Q = int(input())
for q in range(Q):
	q1, q2 = map(int,input().split())
	ans = 0
	ch, cw = nml[q1-1][0], nml[q1-1][1]
	for i in range(q1+d, q2+1, d):
		nh, nw = nml[i-1][0], nml[i-1][1]
		ans += abs(ch-nh)+abs(cw-nw)
		ch, cw = nh, nw
	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())
from itertools import chain
for i in range(Q):
  L, R = map(int, input().split())
  l = divmod(list(chain(*A)).index(L), len(A[0]))
  oldl = l
  ans = 0
  while L != R:
    l = divmod(list(chain(*A)).index(L+D), len(A[0]))
    ans += abs(oldl[0]-l[0])+abs(oldl[1]-l[1])
    L += D
    oldl = l
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
a=[]
for _ in range(h):
    l=list(map(int,input().split()))
    a += l
q=int(input())
command=[]
for _ in range(q):
    l=tuple(map(int,input().split()))
    command.append(l)
route=[]
for k in range(d):
    if k==0:
        k=d
    ind=a.index(k)
    t=0
    l=[]
    i=ind%w
    j=ind//w
    while k<=h*w:
        ind=a.index(k)
        x=ind%w
        y=ind//w
        t += abs(x-i) + abs(y-j)
        l.append(t)
        k += d
        i=x
        j=y
    route.append(l)
    
for i in command:
    start=i[0]
    end=i[1]
    n=start%d
    line=route[n]
    if n==0:
        start -= d
        end -= d
    ans=line[(end-n)//d]-line[(start-n)//d]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + np.sum(np.abs(num[i]-num[i-D]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(H*W-D):
    num_sum[i] = np.sum(np.abs(num[i+D::D]-num[i:H*W-D:D]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[L-1]-num_sum[R-1])
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  num = np.array(num)
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(np.sum(np.abs(num[L+D-1:R+D-1:D]-num[L-1:R-1:D])))
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

A = [[] for _ in range(H)]
for i in range(H):
    A[i] = list(map(int,(input().split())))

d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i,j)

m = [0]*(H*W)
for i in range(1,H*W):
    if i+D <= H*W:
        m[i] = abs(d[i][0] - d[i+D][0]) + abs(d[i][1] - d[i+D][1])

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

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
target = [[0,0] for _ in range(H*W+1)]
ans = 0
for i in range(H):
    for j in range(W):
        target[grid[i][j]][0] = i+1
        target[grid[i][j]][1] = j+1
for i in range(Q):
    tmp = 0
    current = LR[i][0]
    while current != LR[i][1]:
        tmp += abs(target[current][0]-target[current+D][0])+abs(target[current][1]-target[current+D][1])
        current += D
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

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

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
a = []
dict = {}
for i in range(h):
	b = list(map(int, input().split()))
	for j in range(w):
		dict[b[j]] = [i,j]

dist = [0 for i in range(h*w)]
for i in range(1,h*w-d+1):
	dist[i-1] = abs(dict[i+d][1]-dict[i][1]) + abs(dict[i+d][0]-dict[i][0])
q = int(input())
for i in range(q):
	l, r = map(int, input().split())
	cnt = 0
	if l==r:
		print (cnt)
		continue
	for j in range(l,r+1,d):
		cnt += dist[j-1]
	cnt -= dist[r-1]
	print (cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
a = []
dict = {}
for i in range(h):
	b = list(map(int, input().split()))
	for j in range(w):
		dict[b[j]] = [i,j]

q = int(input())
for i in range(q):
	l, r = map(int, input().split())
	cnt = 0
	v =[]
	for j in range(l,r+1,d):
		v.append(dict[j])
	for j in range(len(v)-1):
		cnt += abs(v[j+1][1]-v[j][1]) + abs(v[j+1][0]-v[j][0])
	print (cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
x = [0]*(H*W+1)
y = [0]*(H*W+1)
for k in range(W):
    for l in range(H):
        x[A[l][k]] = k+1
        y[A[l][k]] = l+1

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

Submission status: Time Limit Exceeded

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

h, w, d = [int(x) for x in input().split()]
n = h*w
a = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lr = [[int(x) for x in input().split()] for _ in range(q)]

from collections import defaultdict
b = defaultdict(list)
for i in range(h):
    for j in range(w):
        b[a[i][j] - 1] = [i, j]
g = [[float('inf')]*(h*w) for _ in range(h*w)]
for i in range(n):
    g[i][i] = 0
for i in range(h*w):
    if i + d >= h*w:
        break
    x1, y1 = b[i]
    x2, y2 = b[i + d]
    g[i][i + d] = abs(x1 - x2) + abs(y1 - y2)

"""
ワーシャルフロイド法:O(n^3)
n:頂点数
"""
def warshall_floyd(d):
    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])
    return d

g = warshall_floyd(g)

for i in range(q):
    l, r = lr[i]
    l -= 1
    r -= 1
    print(g[l][r])

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())
d = [[0] * (H*W+1) for i in range(H*W+1)]

# 全ての数字に対応する座標を格納
matrix = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        matrix[A[i][j]] = (i, j)

#print(matrix)
for i in range(1, H*W+1):
    for j in range(i, H*W+1, D):
        if i == j:
            d[i][j] = 0
        else:
            f = matrix[j-D]
            to = matrix[j]
            d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])
    for j in range(i-D,0,-D):
        f = matrix[j+D]
        to = matrix[j]
        d[i][j] = d[i][j+D] + abs(f[0]-to[0]) + abs(f[1]-to[1])

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

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())
d = [[0] * (H*W+1) for i in range(H*W+1)]

# 全ての数字に対応する座標を格納
matrix = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        matrix[A[i][j]] = (i, j)

#print(matrix)
for i in range(1, H*W+1):
    for j in range(i, H*W+1):
        if (j-i) % D != 0: continue
        if i == j:
            d[i][j] = 0
        else:
            f = matrix[j-D]
            to = matrix[j]
            d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])
    for j in range(i-1,0,-1):
        if (j-i) % D != 0: continue
        f = matrix[j+D]
        to = matrix[j]
        d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])

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

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = tuple(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())
Exam = []
maxD = 0
for i in range(Q):
    l, r = map(int, input().split())
    maxD = max(maxD, (r-l))
    Exam.append((l,r))

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, maxD+1, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for l, r in Exam:
    print(DP[l][r])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, H*W, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

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

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, H*W, D):
    for start in range(H*W+1):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

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

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [0] * (H*W+1)
for _ in range(Q):
    ans = 0
    start, end = map(int, input().split())
    while start != end:
        next = start + D
        if DP[start] > 0:
            ans += DP[start]
        else:
            ny, nx = A_where[next]
            y, x = A_where[start]
            an = abs(ny-y) + abs(nx-x)
            DP[start] = an
            ans += an
            start = next
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
A_where = [(-1, -1)]
for i in range(1, H*W+1):
    for j in range(H):
        for k in range(W):
            if A[j][k] == i:
                A_where.append((j, k))

Q = int(input())

DP = [0] * (H*W+1)
for _ in range(Q):
    ans = 0
    start, end = map(int, input().split())
    while start != end:
        next = start + D
        if DP[start] > 0:
            ans += DP[start]
        else:
            ny, nx = A_where[next]
            y, x = A_where[start]
            an = abs(ny-y) + abs(nx-x)
            DP[start] = an
            ans += an
            start = next
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


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


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]

    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        ans = 0
        d = (R - L) // D
        last = M[L]
        for i in range(1, d + 1):
            new = M[L + D * i]
            ans += abs(last[0] - new[0]) + abs(last[1] - new[1])
            last = new
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


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


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]

    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = R - L
        ans = 0
        lh = M[L][0]
        lw = M[L][1]
        while L != R:
            nh = M[L + D][0]
            nw = M[L + D][1]
            ans += abs(nh - lh) + abs(nw - lw)
            L += D
            lh = nh
            lw = nw
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


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


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]

    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = R - L
        ans = 0
        lh = M[L][0]
        lw = M[L][1]
        while d > 0:
            p = M[L + D]
            nh = p[0]
            nw = p[1]
            ans += abs(nh - lh) + abs(nw - lw)
            d -= D
            L += D
            lh = nh
            lw = nw
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  H,W,D = map(int,input().split())
  A = [[] for _ in range(H)]
  posi = [[]] * (H * W)
  
  for _ in range(H):
    a = list(map(int,input().split()))
    A[_] = a
    for i,j in enumerate(a):
      k = i + 1
      t = _ + 1
      posi[j - 1] = [t,k]
  
  Q = int(input())
  
  acdist = [0] * (H * W)
  
  for _ in range(0,H * W - D):
    for d in range(_,H * W - D,D):
      acdist[_] += abs(posi[d + D][0] - posi[d][0]) + abs(posi[d + D][1] - posi[d][1])
  
  for i in range(Q):
    l,r = map(int,input().split())
    print(acdist[l - 1] - acdist[r - 1])
    
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]

Q = int(input())

dist = [0] * (H * W)
acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  for d in range(_,H * W - D,D):
    acdist[_] += abs(posi[d + D][0] - posi[d][0]) + abs(posi[d + D][1] - posi[d][1])

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

Submission status: Time Limit Exceeded

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

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]

Q = int(input())

dist = [0] * (H * W)
acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  dist[_] = abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for d in range(0,H * W - D):
   acdist[d] = sum([dist[i] for i in range(d,H * W,D)])

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

Submission status: Time Limit Exceeded

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

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]


Q = int(input())

for i in range(Q):
  ans = 0
  l,r = map(int,input().split())
  power = 0
  for j in range(l - 1,r - D,D):
    ans += abs(posi[j + D][0] - posi[j][0]) + abs(posi[j + D][1] - posi[j][1])
  print(ans)