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:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


@lru_cache(maxsize=None)
def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(numbers, queries, D):
    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            res = sub_solve(l, l+D)
            ans += res
            l += D
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, D)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

board=np.zeros([h,w],int)

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

q=int(input())

distances=[-1 for _ in range(h*w)]

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

    i,j=np.where(board==1)
    x,y=np.where(board==7)


    res=0
    while(l!=r):
        if distances[l]==-1:
            i,j=np.where(board==l)
            x,y=np.where(board==(l+d))
            distances[l]=abs(i[0]-x[0])+abs(j[0]-y[0])
        res+=distances[l]
        l+=d
    print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i][i+D]
  distances[i%D]+=[d]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(sum(distances[q][l:r]))

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split(" "))
Lx=[0]*(w*h+1);Ly=[0]*(w*h+1);

for i in range(h):
    s=input().split(" ")
    for j in range(w):
        a=int(s[j])
        Lx[a]=j;Ly[a]=i

q=int(input())
for i in range(q):
    p=0
    l,r=map(int,input().split(" "))
    while l != r:
        p+=(abs(Lx[l]-Lx[l+d])+abs(Ly[l]-Ly[l+d]))
        l+=d;
    print(p)

Submission status: Time Limit Exceeded

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

H, W, D = map(int, input().split())
matrix = []
dic = {}
for h in range(H):
  line = list(map(int, input().split()))
  matrix.append(line)
  for idx,w in enumerate(line):
    dic[w] = (idx,h)

_ab_cost = {}
def ab_cost(L, R):
  if (L, R) in _ab_cost.keys():
    return _ab_cost[(L,R)]
  _cost = 0
  while L != R:
    _cost += dist(dic[L], dic[L+D])
    L = L+D
  _ab_cost[(L,R)] = _cost
  return _ab_cost[(L,R)]

Q = int(input())
for q in range(Q):
  L, R = map(int, input().split())
  cost = 0
  if L == R:
    print(cost)
    continue
  cost = ab_cost(L, R)
  print(cost)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0


@lru_cache(maxsize=None)
def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

@lru_cache(maxsize=None)
def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

for pr, ne in way:
    print(solve(pr, ne))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0


def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

for pr, ne in way:
    print(solve(pr, ne))

Submission status: Time Limit Exceeded

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

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

for L,R in LR:
  mpsum = 0
  start = Arev[L]
  for x in range(L, R+1, D):
    next_ = Arev[x]
    mpsum += abs(start[0]-next_[0]) + abs(start[1]-next_[1])
    start = next_
  print(mpsum)

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)]
rA = [[0 for j in range(2)] for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		rA[A[i][j]][0] = i
		rA[A[i][j]][1] = j

Q = int(input())
for i in range(Q):
	L, R = map(int, input().split())
	ans = 0
	for j in range(H * W) [L::D]:
		if j == R:
			break
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	print (ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split(" "))
board = [input().split(" ") for i in range(h)]

q = int(input())
for i in range(q):
    l,r = map(int,input().split(" "))
    n = int((r-l)/d)
    count = 0
    for j in range(n):
        for k in range(h):
            if str(l+j*d) in board[k]:
                x1 = board[k].index(str(l+j*d))
                y1 = k
            if str(l+(j+1)*d) in board[k]:
                x2 = board[k].index(str(l+(j+1)*d))
                y2 = k
        count = count + abs(int(x2)-int(x1)) + abs(y2-y1)
    print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

H, W, D = map(int, input().split())
matrix = []
dic = {}
for h in range(H):
  line = list(map(int, input().split()))
  matrix.append(line)
  for idx,w in enumerate(line):
    dic[w] = (idx,h)

_ab_cost = {}
def ab_cost(L, R):
  if (L, R) in _ab_cost.keys():
    return _ab_cost[(L,R)]
  _ab_cost[(L,R)] = dist(dic[L], dic[L+D])
  return _ab_cost[(L,R)]

Q = int(input())
for q in range(Q):
  L, R = map(int, input().split())
  cost = 0
  if L == R:
    print(cost)
    continue
  while L != R:
    cost += ab_cost(L, R)
    L = L + D
  print(cost)

Submission status: Time Limit Exceeded

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

    a = [(0,0) for i in range(h*w+1)]
    for y in range(h):
        row = list(map(int, input().split()))
        for x, v in enumerate(row):
            a[v] = (x, y)

    q = int(input())

    l, r = [], []

    for i in range(q):
        l_, r_ = map(int, input().split())
        l.append(l_)
        r.append(r_)
    #
    # print(h, w, d)
    # print(a)
    # print(l, r)


    # qi 回目の試験を計算
    for qi in range(q):
        sum_magic = 0
        l_, r_ = l[qi], r[qi]
        #print(l_, r_)
        # mi 回目の移動の魔力
        for mi in range((r_-l_)//d):
            fr = l_ + d * (mi)
            to = l_ + d * (mi+1)

            frx, fry = a[fr]
            tox, toy = a[to]
            dist = abs(frx-tox) + abs(fry-toy)
            # print(mi, fr, to, dist)

            sum_magic += dist
        print(sum_magic)

solve()

Submission status: Time Limit Exceeded

Solution code:
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

for i in range(q):
    power = 0
    pre_number = lr[i][0]
    next_number = lr[i][0] + hwd[2]
    while pre_number != lr[i][1]:
        for j in range(hwd[0]):
            for k in range(hwd[1]):
                if a[j][k] == pre_number:
                    pre_xy = [j, k]
                if a[j][k] == next_number:
                    next_xy = [j, k]
        power = power + abs(pre_xy[0] - next_xy[0]) + abs(pre_xy[1] - next_xy[1])
        pre_number = next_number
        next_number = next_number + hwd[2]
    print(power)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

A = np.array(A)
    
Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    MP = 0
    x = np.where(A == L)[0][0]
    y = np.where(A == L)[1][0]
    
    while L != R:
        L += D
        next_x = np.where(A == L)[0][0]
        next_y = np.where(A == L)[1][0]
        MP += np.absolute(next_x - x) + np.absolute(next_y - y)
        x = next_x
        y = next_y
    
    print(MP)

Submission status: Time Limit Exceeded

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

for i in range(h):
  i+=1
  tmp=list(map(int,input().split()))
  for j in range(w):
    num=tmp[j]
    j+=1
    a[num%d][int( (num-1)/d)]=[i,j]

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  x=-1
  y=-1
  for j in a[l%d][int((l-1)/d):int((r-1)/d)+1]:
    if x==-1:
      x,y=j[0],j[1]
    else:
      ans+=abs(x-j[0])+abs(y-j[1])
      x,y=j[0],j[1]
  print(ans)

Submission status: Time Limit Exceeded

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

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    # for L, R in Qs:
    #     power = 0
    #     while L != R:
    #         i, j = np.where(board == L)
    #         L += D
    #         x, y = np.where(board == L)
    #         power += int(abs(x-i) + abs(y-j))
    #     print(power)

    memo = {}

    for L, R in Qs:
        if L == R:
            print(0)
            continue
        elif (L, R) in memo:
            print(memo[(L, R)])
        nums = np.arange(L, R+D, D)
        arr = np.array([np.array(np.where(board == num)).reshape(-1) for num in nums])
        x_lim, y_lim = np.split(arr, 2, axis=1)
        ans = np.sum(np.abs(x_lim[1:] - x_lim[:-1])) + np.sum(np.abs(y_lim[1:] - y_lim[:-1]))
        print(ans)

        memo[(L, R)] = ans

Submission status: Time Limit Exceeded

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

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

cache = {}

def calc(x, y):
    if (x, y) in cache:
        return cache[(x, y)]
    p1 = pos[x]
    p2 = pos[y]
    r = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    cache[(x, y)] = r
    return r

def calclr(l, r):
    if (l, r) in cache:
        return cache[(l, r)]
    result = 0
    x = l
    while x < r:
        y = x + D
        result += calc(x, y)
        x += D
    cache[(l, r)] = result
    return result

for l, r in LR:
    print(calclr(l, r))

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from functools import lru_cache

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

@lru_cache()
def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = 0
    while l!=r:
        ret += calc(l,l+d)
        l += d
    print(ret)

Submission status: Time Limit Exceeded

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

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split(' '))
    cnt = 0
    x, y = comp[l]
    while l != r:
        l += d
        i, j = comp[l]
        cnt += abs(x - i) + abs(y - j)
        x, y = i, j

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

H,W,D=map(int,input().split())
A=[[-1for i in range(W)]for j in range(H)]
for i in range(H):
    A[i]=list(map(int,input().split()))
Q=int(input())
L=[-1for i in range(Q)]
R=[-1for i in range(Q)]
for i in range(Q):
    L[i],R[i]=map(int,input().split())
    
for i in range(Q):
    MP=0
    x=L[i]
    for j in range(H):
        if(x in A[j]):
            Px=A[j].index(x)
            Py=j
    while(x!=R[i]):
        x+=D
        for j in range(H):
            if(x in A[j]):
                Pnx=A[j].index(x)
                Pny=j
                MP+=abs(Px-Pnx)+abs(Py-Pny)
                Px=Pnx
                Py=Pny
                break
                
    print(MP)


"""
x=[[0,1,2],[3,4,5],[6,7,8]]
for i in range(len(x)):
    if(5 in x[i]):
        print(i,x[i].index(5))
        break
"""

Submission status: Time Limit Exceeded

Solution code:
H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
L = []
R = []
for i in range(Q):
    temp = list(map(int, input().split()))
    L.append(temp[0])
    R.append(temp[1])


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


result = []
for q in range(Q):
    flag = True
    for i in range(q):
        if L[i] == L[q] and R[i] == R[q]:
            cost = result[i]
            flag = False
            break
    if flag:
        pos = [table[i] for i in list(range(L[q], R[q] + 1))[::D]]
        cost = sum([sum([abs(pos[i][j] - pos[i + 1][j]) for j in range(2)]) for i in range(len(pos) - 1)])

    result.append(cost)
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
def search(num):
    for i in range(H):
        for j in range(W):
            if A[i][j]==num:
                return (i,j)

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

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

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

for i in range(Q):
    power=0

    x=L[i]
    while x!=R[i]:
        mFrom=search(x)
        mTo=search(x+D)
        power+=abs(mFrom[0]-mTo[0])+abs(mFrom[1]-mTo[1])
        x+=D
    print(power)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

# for h in range(H):
#     As = list(map(int, input().split()))
#     for w in range(W):
#         Ah[As[w]-1] = h
#         Aw[As[w]-1] = w

for h in range(H):
    As = np.array(list(map(int, raw_input().split())))
    Aw[As-1] = np.arange(W)
    Ah[As-1] = h

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    #print(solve(L, R))
    lrs.append((L,R))

for info in lrs:
    L,R = info
    print(solve(L, R))

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

cost = []
for i in range(h) :
    for j in range(w) :
        cost.append([A[i][j], j+1, i+1])

cost.sort(key=lambda c:c[0])

q = int(input())
for _ in range(q) :
    ans = 0
    l, r = map(int, input().split())
    while l != r :
        x1 = cost[l-1][1]
        y1 = cost[l-1][2]
        x2 = cost[l-1+d][1]
        y2 = cost[l-1+d][2]
        ans += abs(x1-x2) + abs(y1-y2)
        l += d
    else :
        print(ans)

Submission status: Time Limit Exceeded

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

#
def get_pos(N):
    for y in range(H):
        if N in A[y]:
            x = A[y].index(N)
            return (x+1, y+1)


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

    magic = 0
    x, y = get_pos(L)
    #print(x, y)

    while L!=R:
        L += D
        s, t = get_pos(L)
        magic += abs(x-s) + abs(y-t)
        x = s
        y = t

    print(magic)

Submission status: Time Limit Exceeded

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

H, W, D = map(int, input().split())
matrix = []
dic = {}
for h in range(H):
  line = list(map(int, input().split()))
  matrix.append(line)
  for idx,w in enumerate(line):
    dic[w] = (idx,h)

Q = int(input())
for q in range(Q):
  L, R = map(int, input().split())
  cost = 0
  if L == R:
    print(cost)
    continue
  while L != R:
    cost += dist(dic[L], dic[L+D])
    L = L + D
  print(cost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

# for h in range(H):
#     As = list(map(int, input().split()))
#     for w in range(W):
#         Ah[As[w]-1] = h
#         Aw[As[w]-1] = w

for h in range(H):
    As = np.array(list(map(int, raw_input().split())))
    Aw[As-1] = np.arange(W)
    Ah[As-1] = h

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    print(solve(L, R))
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from functools import lru_cache

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

@lru_cache()
def calc(l,r):
    ret = 0
    while l!=r:
        c1 = table[l]
        c2 = table[l+d]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
        l += d
    return ret

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])
    print(calc(l,r))

Submission status: Time Limit Exceeded

Solution code:
def get_index(x):
    for h, col in enumerate(A):
        if x in col:
            return h, col.index(x)


def main():
    global A
    H, W, D = map(int, input().split())
    A = []
    for i in range(H):
        A.append(tuple(map(int, input().split())))
    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        h, w = get_index(L)
        magic = 0
        for n in range(L+D, R+1, D):
            next_h, next_w = get_index(n)
            magic += abs(next_h - h) + abs(next_w - w)
            h, w = next_h, next_w
        print(magic)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a = []
branch = dict()
for i in range(1,h*w+1):
	branch[i] = []
for i in range(h):
	atemp = list(map(int,input().split()))
	for k in range(w):
		branch[atemp[k]].append(i+1)
		branch[atemp[k]].append(k+1)
	a.append(atemp)
q = int(input())
l = []
r = []
for i in range(q):
	ltemp,rtemp = map(int,input().split())
	l.append(ltemp)
	r.append(rtemp)

for i in range(q):
	ans = 0
	now = l[i]
	while now != r[i]:
		ans += abs(branch[now][0]-branch[now+d][0])+abs(branch[now][1]-branch[now+d][1])
		now = now+d
	print(ans)

Submission status: Time Limit Exceeded

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

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    # for L, R in Qs:
    #     power = 0
    #     while L != R:
    #         i, j = np.where(board == L)
    #         L += D
    #         x, y = np.where(board == L)
    #         power += int(abs(x-i) + abs(y-j))
    #     print(power)

    for L, R in Qs:
        nums = np.arange(L, R+D, D)
        arr = np.array([np.array(np.where(board == num)).reshape(-1) for num in nums])
        x_lim, y_lim = np.split(arr, 2, axis=1)
        ans = np.sum(np.abs(x_lim[1:] - x_lim[:-1])) + np.sum(np.abs(y_lim[1:] - y_lim[:-1]))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
L = []
R = []
for i in range(Q):
    temp = list(map(int, input().split()))
    L.append(temp[0])
    R.append(temp[1])


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


for q in range(Q):
    pos = [table[i] for i in list(range(L[q], R[q] + 1))[::D]]
    cost = sum([sum([abs(pos[i][j] - pos[i + 1][j]) for j in range(2)]) for i in range(len(pos) - 1)])
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


@lru_cache(maxsize=None)
def sub_solve(l, r, D):
    ans = 0
    while True:
        if l == r:
            break
        sx, sy = numbers[l]
        gx, gy = numbers[l+D]
        ans += abs(sx - gx) + abs(sy - gy)
        l += D
    return ans


def solve(numbers, queries, D):
    for l, r in queries:
        ans = sub_solve(l, r, D)
        print(ans)

numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, D)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

num_dict = {}

for i in range(1, H + 1):
    line_num = map(int, input().split())
    for j, num in enumerate(line_num):
        num_dict[num] = [i, j+1]

Q = int(input())

cache = {}

for k in range(Q):
    question = input()

    if question in cache:
        print(cache[question])
    else:
        L, R = map(int, question.split())
        result = 0
        while L != R:
            next_L = L + D
            p = num_dict[L]
            n = num_dict[next_L]

            result += abs(p[0] - n[0]) + abs(p[1] - n[1])
            L = next_L

        print(result)
        cache[question] = result

Submission status: Time Limit Exceeded

Solution code:
temp = list(map(int,input().split()))
H = temp[0]
W = temp[1]
D = temp[2]
dic = {}
for i in range(H):
    temp = list(map(int,input().split()))
    for j in range(len(temp)):
        key =  str(i) + " " +  str(j)
        dic[str(temp[j])] = key

Q = int(input())
end = []
for i in range(Q):
    temp = list(map(int, input().split()))
    L = temp[0]
    R = temp[1]
    length = 0
    if L == R:
        print(0)
    #elif L == end[0] and R == end[1]:
        #print(end[2])
    else:
        Lt = L
        for i in range(int((R-L)/D)):
            pre = list(map(int,dic[str(Lt)].split()))
            pro = list(map(int,dic[str(Lt+D)].split()))
            length += abs(pre[0]-pro[0]) + abs(pre[1]-pro[1])
            Lt = Lt+D
        print(length)
        end.append([L,R,length])

Submission status: Time Limit Exceeded

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]
times = int(input())
memo=[0]*90001
for i in range(0, times):
    temp = list(map(int, input().split(" ")))
    nowloc = temp[0]
    ans = 0
    while nowloc != temp[1]:
        if memo[nowloc]==0:
            memo[nowloc]=abs(data[nowloc][0] - data[nowloc + a[2]][0]) + abs(data[nowloc][1] - data[nowloc + a[2]][1])
        ans += memo[nowloc]
        nowloc += a[2]
    print(ans)

Submission status: Time Limit Exceeded

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

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

def calc(x, y, cache={}):
    if (x, y) in cache:
        return cache[(x, y)]
    p1 = pos[x]
    p2 = pos[y]
    r = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    cache[(x, y)] = r
    return r

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        result += calc(x, y)
        x += D
    print(result)

Submission status: Time Limit Exceeded

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

comp = {}
for i in range(h):
    matrix = list(map(int, input().split(' ')))
    for j in range(w):
        comp[matrix[j]] = [i, j]
        
q = int(input())
lr = [list(map(int, input().split(' '))) for _ in range(q)]


for l, r in lr:
    cnt = 0
    x, y = comp[l]
                
    while l != r:
        l = l + d
        i, j = comp[l]
        cnt += abs(x - i) + abs(y - j)
        x, y = i, j
                    
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

for h in range(H):
    As = list(map(int, raw_input().split()))
    for w in range(W):
        Ah[As[w]-1] = h
        Aw[As[w]-1] = w

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    print(solve(L, R))
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
for i in range(1,H*W+1-D):
  for j in range(i+1,H*W+1):
    if (j-i)%D==0:
      dist[i][j] = dist[i][j-D]+dist[j-D][j]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  print(dist[L][R])