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=[]
for i in range(H):
    a=list(map(int,input().split()))
    A.append(a)
Q=int(input())
L=[]
R=[]

lst=[[]for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        lst[A[i][j]].append(i)
        lst[A[i][j]].append(j)
#print(lst)
#print(lst[1][1])
d=[]
for i in range(D):

    if i==0:
        tmp=D
        cnt=[0]*(H*W+1)
        sx=lst[tmp][0]
        sy=lst[tmp][1]
        cnt[tmp]=0
    else:
        tmp=i
        cnt=[0]*(H*W+1)
        #print(tmp)
        sx=lst[tmp][0]
        sy=lst[tmp][1]
        cnt[i]=0
    while(1):
        sx=lst[tmp][0]
        sy=lst[tmp][1]
        tmp=tmp+D
        #print(tmp)
        #この段階？
        #1週目で超える場合
        if tmp>(H*W):
            break
        x=lst[tmp][0]
        y=lst[tmp][1]
        val=abs(sx-x)+abs(sy-y)
        cnt[tmp]=cnt[tmp-D]+val
        if (tmp+D)>(H*W):
            break
    d.append(cnt)
ans=[]
#print(cnt)
#print(d)
for i in range(Q):
    l,r=map(int,input().split())
    ll=l%D
    count=d[ll]
    #print(count)
    vall=count[l]
    valr=count[r]
    val=valr-vall
    #print(val)
    ans.append(val)

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

Submission status: Time Limit Exceeded

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

def find(x):
    for i in range(H):
        for j in range(W):
            if A[i][j]==x:
                return i,j

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    cost=0
    x,y=find(L)
    for j in range(L+D,R+D,D):
        new_x,new_y=find(j)
        cost+=abs(x-new_x)+abs(y-new_y)
        x,y=new_x,new_y
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split(" "))
mass = [[0 for _ in range(W)] for _ in range(H)]
num = [[0,0] for _ in range(H * W + 1)]
DP = [0 for _ in range(H * W + 1)]
for i in range(H):
  mass[i] = list(map(int,input().split(" ")))
for i in range(H):
  for i2 in range(W):
    num[mass[i][i2]] = [i,i2]
for i in range(D,W * H + 1):
  DP[i] = abs(num[i][0] - num[i - D][0]) + abs(num[i][1] - num[i - D][1])
L = 0
R = 0
ans = 0
Q = int(input())
for i in range(Q):
  ans = 0
  L,R = map(int,input().split(" "))
  while L != R:
    L += D
    ans += DP[L]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
num=[]
for i in range(h):
    num += list(map(int,input().split()))
q=int(input())
ans=[]
for n in range(q):
    sum=0
    l,r=map(int,input().split())
    ind=num.index(l)
    i=ind//w+1
    j=ind%w+1
    for m in range((r-l)//d):
        l += d
        ind=num.index(l)
        x=ind//w+1
        y=ind%w+1
        sum += abs(x-i)+abs(y-j)
        i=x
        j=y

    ans.append(sum)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
num=[]
for i in range(h):
    num += list(map(int,input().split()))
q=int(input())
ans=[]
for i in range(q):
    sum=0
    l,r=map(int,input().split())
    ind=num.index(l)
    i=ind//w+1
    j=ind%w+1
    while l!=r:
        l += d
        ind=num.index(l)
        x=ind//w+1
        y=ind%w+1
        sum += abs(x-i)+abs(y-j)
        i=x
        j=y
    ans.append(sum)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    cnt = s
    res = 0
    while cnt < g:
        x = dic[cnt + d][0] - dic[cnt][0]
        y = dic[cnt + d][1] - dic[cnt][1]
        res += abs(x) + abs(y)
        cnt += d
    print(res)

Submission status: Time Limit Exceeded

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

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

C = [[] for _ in range(H * W)]

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

# print(C)

for l, r in lr:
    ans = 0
    while l < r:
        i, j = C[l - 1]
        x, y = C[l - 1 + D]
        ans += abs(x - i) + abs(y - j)
        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)]
C = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i,j)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    cost = 0
    i,j = C[L]
    while L!=R:
        L+=D
        x,y = C[L]
        cost += abs(x-i)+abs(y-j)
        i,j = C[L]
    print(cost)

Submission status: Time Limit Exceeded

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

h, w, d = [int(x) for x in input().split()]
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)]

dic = {}

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

for i in range(q):
    l, r = lr[i]
    res = 0
    while l < r:
        res += abs(dic[l][0] - dic[l + d][0]) + abs(dic[l][1] - dic[l + d][1])
        l += d
    print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k+d < h*w:
        x0, y0 = X[k]
        x1, y1 = X[k+d]
        D.append(abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for k in range(l-1, r-1, d):
        ans += D[k]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(G, a, b):
    # グラフGにおいてaからbへの距離
    # 到達不可能な場合は-1を返す
    n = len(G)
    d = [-1] * n
    que = deque([a])
    d[a] = 0
    while que:
        x = que.popleft()
        if x == b:
            return d[b]
        next = G[x]
        for y in next:
            if d[y] == -1:
                que.append(y)
                d[y] = d[x] + 1
    return d[b]


h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for i in range(h)]
G = [[] for k in range(h*w)]
for i in range(h):
    for j in range(w):
        if i > 0:
            G[A[i][j]-1].append(A[i-1][j]-1)
        if i < h-1:
            G[A[i][j]-1].append(A[i+1][j]-1)
        if j > 0:
            G[A[i][j]-1].append(A[i][j-1]-1)
        if j < w-1:
            G[A[i][j]-1].append(A[i][j+1]-1)
D = []
for k in range(h*w):
    if k+d < h*w:
        D.append(bfs(G, k, k+d))

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = 0
    for k in range(l-1, r-1, d):
        x += D[k]
    print(x)

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())
X=[[[0,0] for _ in range((H*W)//D+1)] for _ in range(D)]
for i in range(H):
    for j in range(W):
        X[A[i][j]%D][A[i][j]//D][0]=i
        X[A[i][j]%D][A[i][j]//D][1]=j

for i in range(Q):
    L,R=map(int,input().split())
    ans=0
    for j in range(L//D,R//D):
        ans+=abs(X[L%D][j][0]-X[L%D][j+1][0])+abs(X[L%D][j][1]-X[L%D][j+1][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#089_D
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
idx = {}
for x in range(0, h):
    for y in range(0, w):
        idx[a[x][y]] = (x, y)
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    cur = l
    ans = 0
    while cur != r:
        cur_x, cur_y = idx[cur]
        to_x, to_y = idx[cur + d]
        ans += abs(cur_x - to_x) + abs(cur_y - to_y)
        cur += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
loc={}
E={}
for i in range(H):
  a=list(map(int,input().split()))
  for j in range(W):
    v=a[j]
    loc[v]=(i,j)
    if v-D in loc.keys():
      i2,j2=loc[v-D]
      E[((i2,j2),(i,j))]=abs(i-i2)+abs(j-j2)
    if v+D in loc.keys():
      i2,j2=loc[v+D]
      E[((i,j),(i2,j2))]=abs(i-i2)+abs(j-j2)
Q=int(input())
for i in range(Q):
  ans=0
  x,y=map(int,input().split())
  if x==y:
    print(0)
  else:
    while x!=y:
      I=loc[x]
      x+=D
      J=loc[x]
      if (I,J) in E.keys():
        ans+=E[(I,J)]
      else:
        i1,j1=I
        i2,j2=J
        v=abs(i1-i2)+abs(j1-j2)
        ans+=v
        E[(I,J)]=v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
loc={}
for i in range(H):
  a=list(map(int,input().split()))
  for j in range(W):
    loc[a[j]]=(i,j)
Q=int(input())
for i in range(Q):
  ans=0
  x,y=map(int,input().split())
  if x==y:
    print(0)
  else:
    while x!=y:
      if ans==0:
        i1,j1=loc[x]
        i2,j2=loc[x+D]
        ans+=(abs(i1-i2)+abs(j1-j2))
        prev=(i2,j2)
        x+=D
      else:
        x+=D
        i1,j1=prev
        i2,j2=loc[x]
        ans+=(abs(i1-i2)+abs(j1-j2))
        prev=(i2,j2)
    print(ans)

Submission status: Time Limit Exceeded

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

# W_max = (W)
fields = [0] * (W*H+1)
# 一列にして、保存しておこうか。
for i in range(H):
    rows = list(map(int, input().split()))
    for j,r in enumerate(rows):
        ind = i * W + j
        fields[r] = ind 
# 各Dにおいて累積和
def calc(l,r):
    cnt = 0
    for i in range(l+D,r+1,D):
        indl = fields[i-D]
        hl = indl // W
        wl = indl % W
        indr = fields[i]
        hr = indr // W
        wr = indr % W
        d = abs(hl-hr) + abs(wl-wr)
        cnt += d
        # print(hl,wl,hr,wr,d)
    return cnt
### query
Q = int(input())
for _ in range(Q):
    L,R = map(int, input().split())
    print(calc(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())
B=[list(map(int,input().split())) for _ in range(Q)]
C=[[]for i in range(H*W)]
for i in range(H):
  for j in range(W):
    a=A[i][j]
    C[a-1].append((j+1,i+1))

for a,b in B:
  cnt=0
  m=(b-a)//D
  for i in range(m):
    start=a+D*(i)
    goal=start+D
    s=C[start-1][0][0]
    t=C[start-1][0][1]
    u=C[goal-1][0][0]
    v=C[goal-1][0][1]
    cnt+=abs(s-u)+abs(t-v)
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

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

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [[0]*(n+1) for _ in range(n+1)]
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d][i] = D[j][i] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        modd = l%d
        print(D[r][modd] - D[l][modd])        

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

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

    idx = [0]*(1+n)
    for i in range(1,h+1):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i,j+1)
    idx[0] = idx[d]

    D = [[0]*(n+1) for _ in range(n+1)]
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        num = i
        while num <= n - d:
            D[num + d][i] = D[num][i] + dist(num,num + d)
            num += d
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        modd = l%d
        print(D[r][modd] - D[l][modd])        

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)]
    S = [0] * (H*W + 1)

    dic = [(-1, -1) for i in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


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)]
    S = [0] * (H*W + 1)

    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)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A = [[0]*W for i in range(H)]
data = [0]*(H*W+1)

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

for i in range(H):
    for j in range(W):
        data[A[i][j]] = [i,j]

Q = int(input())

L = [0] * Q
R = [0] * Q

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


for i in range(Q):
    ans = 0
    x = L[i]
    while x != R[i]:
        ans += abs(data[x+D][0]-data[x][0])
        ans += abs(data[x+D][1]-data[x][1])
        x += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
##解答を見た
import sys
def input(): return sys.stdin.readline().strip()

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

pos = []
for k in range(1,H*W+1):
    for i in range(H):
        for j in range(W):
            if A[i][j] == k:
                pos.append([i+1,j+1])
                break
dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i-1][0]-pos[i-D-1][0])+abs(pos[i-1][1]-pos[i-D-1][1]))

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

for i in range(Q):##O(Q)
    print(dist[LR[i][1]-1]-dist[LR[i][0]-1])

Submission status: Time Limit Exceeded

Solution code:
##解答を見た O(HW)+O(HW)+O(Q) ~ O(Q)

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

pos = []
for k in range(1,H*W+1):##O(HW)
    for i in range(H):
        for j in range(W):
            if A[i][j] == k:
                pos.append([i+1,j+1])
                break
dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i-1][0]-pos[i-D-1][0])+abs(pos[i-1][1]-pos[i-D-1][1]))
def exam(L,R):##O(1)
    """
    ans = 0
    while R != L:
        ##print("L",L,"R",R)
        ans += abs(dist[L+D-1][0]-dist[L-1][0])+abs(dist[L+D-1][1]-dist[L-1][1])
        L += D
    """
    return dist[R-1] - dist[L-1]  

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

for i in range(Q):##O(Q)
    print(exam(LR[i][0],LR[i][1]))

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = []
for i in range(H):
    tmp = list(map(int,input().split()))
    A.append(tmp)
dist = []
for k in range(1,H*W+1):
    for i in range(H):
        for j in range(W):
            if A[i][j] == k:
                dist.append([i+1,j+1])
                break
def exam(L,R,D):
    ans = 0
    while R != L:
        ##print("L",L,"R",R)
        ans += abs(dist[L+D-1][0]-dist[L-1][0])+abs(dist[L+D-1][1]-dist[L-1][1])
        L += D
    return ans    

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

for i in range(Q):
    print(exam(LR[i][0],LR[i][1],D))

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
A_ij = [(0,0,0)]
for i in range(h):
    a_i = list(map(int,input().split()))
    for j in range(w):
        num = a_i[j]
        A_ij.append((num,i,j))
A_ij.sort()
q = int(input())
for _ in range(q):
    start,end = map(int,input().split())
    points = [A_ij[i] for i in range(start,end+1,d)]
    ans = 0
    for i in range(len(points)-1):
        ans += abs(points[i+1][1] - points[i][1])
        ans += abs(points[i+1][2] - points[i][2])
    print(ans)

Submission status: Time Limit Exceeded

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

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

q = int(input())
for j in range(q):
    begin, end = map(int, input().split())
    total = 0
    while(begin != end):
        C = A[begin - 1]
        D = A[begin+d - 1]
        total += abs(D[0] - C[0]) + abs(D[1] - C[1])
        begin = begin + d
    print(total)

Submission status: Time Limit Exceeded

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

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

Inds = {x:[] for x in range(1, h*w+1)}
for j in range(h):
    for k in range(w):
        Inds[A[j][k]].append(j)
        Inds[A[j][k]].append(k)
# print(Inds)

for lr in LR:
    l = lr[0]
    r = lr[1]
    now = l
    ans = 0
    while now < r:
        # print('y is' + str(Inds[now-1][0]))
        # print('x is' + str(Inds[now-1][1]))
        ans += abs(Inds[now][0]-Inds[now+d][0]) + abs(Inds[now][1]-Inds[now+d][1])
        now += d
    print(ans)

Submission status: Time Limit Exceeded

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

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

Inds = []
for i in range(h*w):
    for j in range(h):
        for k in range(w):
            if A[j][k] == i+1:
                Inds.append([j,k])
# print(Inds)

for lr in LR:
    l = lr[0]
    r = lr[1]
    now = l
    ans = 0
    while now < r:
        # print('y is' + str(Inds[now-1][0]))
        # print('x is' + str(Inds[now-1][1]))
        ans += abs(Inds[now-1][0]-Inds[now+d-1][0]) + abs(Inds[now-1][1]-Inds[now+d-1][1])
        now += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def move(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])
h,w,d=map(int,input().split())
dict={}
for i in range(1,h*w+1):
  dict.update({i:(0,0)})
a=[]
for _ in range(h):
  tmp=list(map(int,input().split()))
  a.append(tmp)
for i in range(h):
  for j in range(w):
    dict[a[i][j]]=(i+1,j+1)
q=int(input())
lr=[]
for _ in range(q):
  tmp=list(map(int,input().split()))
  lr.append(tmp)
for t in lr:
  dist=0
  l,r = t[0],t[1]
  x=l
  while(x!=r):
    dist+=move(dict[x],dict[x+d])
    x+=d
  print(dist)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache as cache

H, W, D = map(int, input().split())
A = tuple(tuple(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]] = (i, j)

def L1(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

@cache(maxsize=None)
def solve(l, r):
    total = 0
    for i in range(l, r, D):
        if costs[i] == -1:
            costs[i] = L1(pos[i], pos[i + D])
        total += costs[i]
    return total

Q = int(input())
for _ in range(Q):
    print(solve(*map(int, input().split())))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = tuple(tuple(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]] = (i, j)

def L1(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

def solve(l, r):
    total = 0
    for i in range(l, r, D):
        if costs[i] == -1:
            costs[i] = L1(pos[i], pos[i + D])
        total += costs[i]
    return total

Q = int(input())
for _ in range(Q):
    print(solve(*map(int, input().split())))

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int,input().split())))
P = dict()
for i in range(H):
    for j in range(W):
        P[A[i][j]] = (i,j)
Q = int(input())
for i in range(Q):
    ans = 0
    L,R = map(int,input().split())
    for j in range(L+D,R+1,D):
        current_pos = P[j-D]
        next_pos = P[j]
        ans += abs(current_pos[0]-next_pos[0])+abs(current_pos[1]-next_pos[1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W,D = map(int,input().split())
A = []
for h in range(H):
  A = A + list(map(int,input().split()))
for i in range(H*W):
  A[i]=(A[i], i, i%W, i//W)
A.sort()

Q = int(input())
for q in range(Q):
  L,R = map(int,input().split())
  ret = 0
  x0,y0=A[L-1][2],A[L-1][3]
  for l in range((R-L)//D):
    x,y=A[L+D*(l+1)-1][2],A[L+D*(l+1)-1][3]
    ret += abs(x-x0)+abs(y-y0)
    x0,y0=x,y
  print(ret)

Submission status: Time Limit Exceeded

Solution code:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

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

for l,r in al:
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)

Submission status: Time Limit Exceeded

Solution code:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)

Submission status: Time Limit Exceeded

Solution code:
n,m,d = map(int, input().split())

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

q = int(input())

buf = {}

for j in range(n):
    for k in range(m):
        buf[grid[j][k]] = (j,k)

for _ in range(q):
    l,r = map(int, input().split())
    prev_x= -1
    prev_y = -1
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)

Submission status: Time Limit Exceeded

Solution code:
n,m,d = map(int, input().split())

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

q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    prev_x= -1
    prev_y = -1
    s = 0

    for j in range(l,r+1,d):
        for k in range(n):
            if j in grid[k]:
                y = (grid[k].index(j))+1
                x = k+1
                break
        if prev_x == -1 and prev_y == -1:
            prev_x = x
            prev_y = y
        else:
            s += abs(prev_x-x) + abs(prev_y-y)
            prev_x = x
            prev_y = y
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B = sorted(B, key=lambda x: x[0])
C = [b[0] for b in B]

import bisect

for i in range(int(input())):

    l, r = [int(_) for _ in input().split()]
    pre = None
    pre_n = 0
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l, pre_n)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        pre_ni = ni
        l = l + D
        pre = (B[ni][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B = sorted(B, key=lambda x: x[0])
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B.sort()
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline

######################################################

INF = 1e10

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B.sort()
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
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(1, h+1):
    for j, a in enumerate(map(int, input().split())):
        mass[a][0] += i
        mass[a][1] += 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
import sys
input = sys.stdin.readline
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(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
import sys
input = sys.stdin.readline
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(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
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
h, w, d = map(int, readline().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(map(int, readline().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])