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:
h,w,d=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(h)]
t={}
for i in range(h):
    for j in range(w):
        t[a[i][j]]=(i,j)

q=int(input())
for i in range(q):
    chk=0
    l,r=map(int,input().split())
    o,p=t[l]
    for j in range(300):
        if l==r: break
        chk+=abs(o-t[l+d][0])+abs(p-t[l+d][1])
        o=t[l+d][0]
        p=t[l+d][1]
        l+=d
    print(chk)

Submission status: Time Limit Exceeded

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

for y in range(H):
    position = list(map(int, input().split()))
    for x in range(W):
        positions[position[x]-1] = [x, y]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

# 各数値の書かれている位置, 1-indexed
X = [0] * (N+1)
Y = [0] * (N+1)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

X = np.array(X,dtype=np.int64)
Y = np.array(Y,dtype=np.int64)

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


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

print('\n'.join(map(str,output)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

# 各数値の書かれている位置, 1-indexed
X = np.zeros(N+1,dtype=np.int64)
Y = np.zeros(N+1,dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


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

print('\n'.join(map(str,output)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

# 各数値の書かれている位置, 1-indexed
X = np.zeros(N+1,dtype=np.int64)
Y = np.zeros(N+1,dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# 各数値の書かれている位置, 1-indexed
X = np.zeros(N+1,dtype=np.int64)
Y = np.zeros(N+1,dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


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

Submission status: Time Limit Exceeded

Solution code:
from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
for i in range(h):
    tmp=[]
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r-d+1,d):
        ans+=sum(abs(s-t)for s,t in zip(g[j],g[j+d]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
for i in range(h):
    tmp=[]
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r-d+1,d):
        ans+=sum(abs(s-t)for s,t in zip(g[j],g[j+d]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
k=0
d={}
for i in range(H):
  l=list(map(int,input().split()))
  for j in range(W):
    k+=1
    d[l[j]]=(i,j)
Q=int(input())
for i in range(Q):
  ans=0
  L,R=map(int,input().split())
  
  n=(R-L)//D
  ans+=sum(abs(d[L+i*D][0]-d[L+(i+1)*D][0])+abs(d[L+i*D][1]-d[L+(i+1)*D][1]) for i in range(n))
    
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    ans+=Dist(l+j*d,l+(j+1)*d)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    ans+=Dist(l+j*d,l+(j+1)*d)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

q=I()
for w in range(q):
    ans=0
    l,r=IL()
    for i in range((r-l)//d):
        
        ans+=abs(Al[l+d*i][0]-Al[l+d*(i+1)][0])+abs(Al[l+d*i][1]-Al[l+d*(i+1)][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
k=0
d={}
e={}
for i in range(H):
  l=list(map(int,input().split()))
  for j in range(W):
    k+=1
    d[l[j]]=(i,j)
Q=int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def dist(ai:int, bi:int, aj:int, bj:int):
    return abs(ai-aj)+abs(bi-bj)

h, w, d = map(int, input().split())
p = {}
for i in range(h):
    tmpstr = input().split()
    for j in range(w):
        tmpchar = int(tmpstr[j])
        p[tmpchar] = (i, j)

q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    curnum = l
    t = (r-l)//d
    for _ in range(t):
        curl, curr = p[curnum]
        nextl, nextr = p[curnum+d]
        ans += dist(curl, curr, nextl, nextr)
        curnum += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dist(ai:int, bi:int, aj:int, bj:int):
    return abs(ai-aj)+abs(bi-bj)

h, w, d = map(int, input().split())
p = {}
for i in range(h):
    tmpstr = input().split()
    for j in range(w):
        tmpchar = int(tmpstr[j])
        p[tmpchar] = (i, j)

q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    curnum = l
    t = (r-l)//d
    for _ in range(t):
        curl, curr = p[curnum]
        nextl, nextr = p[curnum+d]
        ans += dist(curl, curr, nextl, nextr)
        curnum += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]-1] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


for i in range(Q):
    ans = 0
    now = A[LR[i][0]-1]
    for j in range(D,LR[i][1] - LR[i][0]+D,D):
        will = A[LR[i][0]-1+j]
        ans += (abs(will[0] - now[0]) + abs(will[1] - now[1]))
        now = will

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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())
for i in range(q):
    l,r = map(int,input().split())
    res = 0
    for s in range(h):
        for t in range(w):
            if A[s][t] == l:
                y1 = s
                x1 = t
    while l != r:
        l += d
        for hh in range(h):
            for ww in range(w):
                if A[hh][ww] == l:
                    y2 = hh
                    x2 = ww
        res += abs(x2-x1)+abs(y2-y1)
        y1 = y2
        x1 = x2
    print(res)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
A=[list(map(int, input().split())) for _ in range(H)]
Am=[None]*(H*W+1)
for h in range(H):
	for w in range(W):
		Am[A[h][w]] = (h, w)
Q=int(input())
for _ in range(Q):
	L,R=map(int, input().split())
	h,w=Am[L]
	ans=0
	for i in range(L, R+1, D):
		ch,cw=Am[i]
		ans+=abs(ch-h)+abs(cw-w)
		h,w=ch,cw
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)

Q=int(input())
#累積和を求める
li = [0]*(H*W+2)
#print(H*W+2)
for i in range(1,D+1):
    #print('i=',i)
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        #print(j)
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
        
        #print("diff",h_,w_)

        #print(j)
    
#print(li)
'''for i in range(1,26,4):
    print(i,li[i])
'''
# ここから計算
L = 17
R=25
#print(li[R]-li[L])
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)

Q=int(input())
#累積和を求める
li = [0]*(H*W+2)
#print(H*W+2)
for i in range(1,D+1):
    #print('i=',i)
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        #print(j)
       
        li[j] = li[j-D]+abs(h_ - int(np.where(f==j)[0]))+abs(w_ - int(np.where(f==j)[1]))
        h_=int(np.where(f==j)[0])
        w_=int(np.where(f==j)[1])
        #print("diff",h_,w_)

        #print(j)
    
#print(li)
'''for i in range(1,26,4):
    print(i,li[i])
'''
# ここから計算
L = 17
R=25
#print(li[R]-li[L])
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
where = [None] * (H*W+1)
for i in range(H):
    inputing = [int(i) for i in input().split()]
    for j in range(W):
        where[int(inputing[j])] = (i, j)
Q = int(input())

for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    now = l
    while now != r:
        ans += abs(where[now][0]-where[now+D][0]) + \
            abs(where[now][1]-where[now+D][1])
        now += D
    print(ans)

Submission status: Time Limit Exceeded

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

size = h * w
dist = [[0] * ((size)//d + 1) for _ in range(d)]

def get_dist(x, y):
  for i, line in enumerate(a):
    if x in line:
      xid = [i, line.index(x)]
    if y in line:
      yid = [i, line.index(y)]
  distance = abs(xid[0] - yid[0]) + abs(xid[1] - yid[1])
  return distance

for i in range(d):
  for j in range((size)//d + 1):
    if (j-1)*d+i <= 0:
      continue
    if j*d + i > size:
      continue
    dist[i][j] = dist[i][j-1] + get_dist(j*d+i, (j-1)*d+i)

for l, r in lr:
  print(dist[r%d][r//d] - dist[l%d][l//d])

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
 

H,W,D = map(int, input().split())
An = {}
for i in range(H):
  s = list(map(int, input().split()))
  for j in range(W):
    An[s[j]] = [i,j]

Q = int(input())
ans = [0]*Q

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

for j in range(Q):
  print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    costs = []
    for i in range(n):
        if i < d:
            costs.append(diff[i])
        else:
            costs.append(diff[i] + costs[i - d])
    return "\n".join([str(costs[r - 1] - costs[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s in range(n):
        if sum(costs[s]) == 0:
            continue
        for g in range(n):
            if costs[s][g] == 0:
                continue
            if s - d >= 0:
                costs[s][g] = costs[s - d][g] - costs[s - d][s]
                continue
            before = 0 if g - d < 0 else costs[s][g - d]
            costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                       index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s, g in product(range(n), repeat=2):
        if costs[s][g] == 0:
            continue
        if s - d >= 0:
            costs[s][g] = costs[s - d][g] - costs[s - d][s]
            continue
        before = 0 if g - d < 0 else costs[s][g - d]
        costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                   index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s, g in product(range(n), repeat=2):
        if costs[s][g] == 0:
            continue
        before = 0 if g - d < 0 else costs[s][g - d]
        costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                   index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    dist = [[0 for i in range(n+1)] for i in range(D)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        k = i%D
        j = i//D
        dist[k][j+1] = dist[k][j]+abs(y_-y)+abs(x_-x)
    q = I()
    for i in range(q):
        l,r = LI()
        k = l%D
        print(dist[k][r//D]-dist[k][l//D])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def dijkstra(s,g):
        k = s%D
        if k == 0:k = D
        if dist[k][g] != float("inf"):
            return dist[k][g]-dist[k][s]
        q = [[0,k]]
        while q:
            dx,x = heappop(q)
            for y,dy in v[x]:
                if dx+dy < dist[k][y]:
                    dist[k][y] = dx+dy
                    heappush(q,[dist[k][y],y])
        return dist[k][g]-dist[k][s]

    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    v = [[] for i in range(n+1)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        v[i].append([i+D,abs(y_-y)+abs(x_-x)])
    dist = [[float("inf") for i in range(n+1)] for i in range(D+1)]
    for i in range(D+1):
        dist[i][i] = 0
    q = I()
    for i in range(q):
        l,r = LI()
        print(dijkstra(l,r))
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def dijkstra(s,g):
        dist = [float("inf") for i in range(n+1)]
        dist[s] = 0
        q = [[0,s]]
        while q:
            dx,x = heappop(q)
            if x == g:
                return dist[x]
            for y,dy in v[x]:
                if dx+dy < dist[y]:
                    dist[y] = dx+dy
                    heappush(q,[dist[y],y])
        return dist[g]

    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    v = [[] for i in range(n+1)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        v[i].append([i+D,abs(y_-y)+abs(x_-x)])
    q = I()
    for i in range(q):
        l,r = LI()
        print(dijkstra(l,r))
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

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

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


Q = int(input())
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    if l == r:
        print(ans)
        continue
    a, b = L[l - 1]
    while L[r - 1] != L[l + D - 1]:
        c, d = L[l - 1 + D]
        ans += abs(a - c) + abs(b - d)
        a, b = L[l + D - 1]
        l = l + D
    e, f = L[r - 1]
    ans += abs(a - e) + abs(b - f)
    print(ans)

Submission status: Time Limit Exceeded

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

    x = [0 for _ in range(90001)]
    y = [0 for _ in range(90001)]
    for i, row in enumerate(A):
        for j, a in enumerate(row):
            x[a] = j
            y[a] = i

    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        m = 0
        while L != R:
            m += abs(x[L] - x[L + D]) + abs(y[L] - y[L + D])
            L += D
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        i = 0
        j = 0
        x = [0 for _ in range(90001)]
        y = [0 for _ in range(90001)]
        for i, row in enumerate(A):
            for j, a in enumerate(row):
                x[a] = j
                y[a] = i
        m = 0
        while L != R:
            m += abs(x[L] - x[L + D]) + abs(y[L] - y[L + D])
            L += D
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().split())
    M = [0 for _ in range(100000)]
    for i in range(H):
        for j, v in enumerate(list(map(int, input().split()))):
            M[v] = (i, j)
    Q = int(input())
    P = []
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            P.append(M[L])
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = [0 for _ in range(100000)]
    for i, row in enumerate(A):
        for j, v in enumerate(row):
            M[v] = (i, j)
    Q = int(input())
    P = []
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            P.append(M[L])
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

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


def f(L):
    i = 0
    j = 0
    while H > i:
        while W > j:
            if A[i][j] == L:
                memo[L] = (i + 1, j + 1)
                P.append((i + 1, j + 1))
                return L
            j += 1
        i += 1
        j = 0
    return 0


def main():
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            if L in memo:
                P.append(memo[L])
            else:
                f(L)
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

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


def f(L):
    i = 0
    j = 0
    while H > i:
        while W > j:
            if A[i][j] == L:
                P.append((i + 1, j + 1))
                return L
            j += 1
        i += 1
        j = 0
    return 0


def main():
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        if L == R:
            ans.append(0)
            continue
        while True:
            f(L)
            if L == R:
                break
            L += D
        m = 0
        for i in range(len(P) - 1):
            m += abs(P[i][0] - P[i + 1][0]) + abs(P[i][1] - P[i + 1][1])
        ans.append(m)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

def func(a, b):
    if dp[a][b]:
        return dp[a][b]

    for i in range(a, b+1, d):
        if a == b:
            dp[a][b] = 0
            return dp[a][b]
        elif i == a:
            dp[a][i] = 0
        else:
            dp[a][i] = dp[a][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

    for i in range(a, b+1, d):
        for j in range(i, b+1, d):
            dp[i][j] = dp[a][j]-dp[a][i]
    return dp[a][b]

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = func(a, b)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

for key in p.keys():
    for i in range(key, h*w+1, d):
        if key == i:
            dp[key][i] = 0
        else:
            dp[key][i] = dp[key][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[a][b]
    print(ans)