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())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i+1,j+1]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    point=[]
    ans=0
    if x-y==0:print(0);continue
    try:
        for i in range(x,y+1,d):
            point.append(adress[i])
        for j in range(len(point)-1):
            ans +=abs(point[j+1][0]-point[j][0])+abs(point[j+1][1]-point[j][1])
        print(ans)
    except:print(0)

Submission status: Time Limit Exceeded

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

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

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    mem = [[None for i in range(W*H + 1)] for i in range(W*H + 1)]

    for i in range(Q):
        l, r = map(int, input().split())
        if mem[l][r] != None:
            print(mem[l][r])
        else:
            ans = 0
            for t in range(l, r, D):
                ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
            print(ans)
            mem[l][r]

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    # mem = [[None for i in range(W)] for i in range(H)]

    for i in range(Q):
        l, r = map(int, input().split())
        # if mem[l][r] != None:
        #     print(mem[l][r])
        # else:
        ans = 0
        for t in range(l, r, D):
            ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
        print(ans)
        # mem[l][r]

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a = [[0 for _ in range(w)] for _ in range(h)]
masu = {}
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j in range(w):
        masu[a[i][j]] = (i,j)

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


q = int(input())
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        ans[i] = 0
    else:
        ans[i] = sum(point[l:r:d])
 
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

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

a = [[0 for _ in range(w)] for _ in range(h)]

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

masu = {}
for i in range(h):
    for j in range(w):
        masu[a[i][j]] = (i,j)

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


q = int(input())
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        ans[i] = 0
    else:
        ans[i] = sum(point[l:r:d])
 
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC89 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*(h*w+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    X,Y = s[i]
    Z,W = s[i-d]
    x = abs(X - Z) + abs(Y - W)
    D[i%d][i//d] = x + D[i%d][i//d-1]
for _ in range(q):
    l,r = map(int,input().split())
    print(D[l%d][r//d] - D[l%d][l//d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC89 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*(h*w+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    x = abs(s[i][0] - s[i-d][0]) + abs(s[i][1] - s[i-d][1])
    D[i%d][i//d] = x
for i in range(d):
    D[i] = list(accumulate(D[i]))
for _ in range(q):
    l,r = map(int,input().split())
    print(D[l%d][r//d] - D[l%d][l//d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC89 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
for _ in range(q):
    cost = 0
    l,r = map(int,input().split())
    while l + d <= r:
        x,y = s[l]
        n,m = s[l+d]
        cost += abs(x-n)+abs(y-m)
        l += d
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H,W,D = (map(int,input().split(" ")))
As = []
dic  = {}
for h in range(H):
    As = tuple((map(int,input().split(" "))))
    for w,A in enumerate(As):
        dic[A] = (h,w)

# print(dic)

Q = int(input())
qs =tuple(tuple((map(int,input().split(" ")))) for _ in range(Q))

for L,R in qs:
    ans = 0
    for i in range(L + D  , R + 1 , D):
        x1,y1 = dic[i]
        x2,y2 = dic[i - D]
        ans += abs(x1-x2) + abs(y1-y2)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H,W,D = (map(int,input().split(" ")))
As = []
dic  = {}
for h in range(H):
    As = list((map(int,input().split(" "))))
    for w,A in enumerate(As):
        dic[A] = (h,w)

# print(dic)

Q = int(input())
qs = [ list((map(int,input().split(" ")))) for _ in range(Q)]

for L,R in qs:
    ans = 0
    for i in range(L + D  , R + 1 , D):
        x1,y1 = dic[i]
        x2,y2 = dic[i - D]
        ans += abs(x1-x2) + abs(y1-y2)

    print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(1, H+1) :
    line = list(map(int, input().split()))
    for j in range(1, W + 1) :
        A[line[j - 1]] = (i, j)

memo = [[-1 for _ in range(H * W + 1)] for _ in range(H * W + 1)]

def cost(nowPoint, endPoint) :
    if nowPoint == endPoint :
        return 0
    if memo[nowPoint][endPoint] >= 0 :
        return memo[nowPoint][endPoint]

    nextPoint = nowPoint + D

    nowCost = abs(A[nextPoint][0] - A[nowPoint][0]) + abs(A[nextPoint][1] - A[nowPoint][1])
    nowCost += cost(nextPoint, endPoint)

    memo[nowPoint][endPoint] = nowCost
    return nowCost

Q = int(input())

for _ in range(Q) :
    start, end = map(int, input().split())
    print(cost(start, end))

Submission status: Time Limit Exceeded

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

q = int(input())
memo = [0 for x in range(h*w+1)]
for i in range(q):
    ans = 0
    l, r = map(int, input().split())
    while l != r:
        if memo[l+d] == 0:
            memo[l+d] = abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])
        ans += memo[l+d]
        l += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]-1] = (i, j)

#    print(x_map)

    q = int(input())

    mp = 0
    for _ in range(q):
        l, r = map(int, input().split())
        for current_pos in range(l+d-1, r, d):
            cp = x_map[current_pos]
            pp = x_map[current_pos-d]
#            print("curre_pos : {0}".format(current_pos))
#            print("cp : {0}".format(cp))
#            print("pp : {0}".format(pp))
            mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
        print(mp)
        mp = 0


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from numpy import array


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]-1] = (i, j)

#    print(x_map)

    q = int(input())

    mp = 0
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        for current_pos in range(l+d-1, r, d):
            cp = x_map[current_pos]
            pp = x_map[current_pos-d]
#            print("curre_pos : {0}".format(current_pos))
#            print("cp : {0}".format(cp))
#            print("pp : {0}".format(pp))
            mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
        ans.append(mp)
        mp = 0

    ans = array(ans)

    for k in range(q):
        print(ans[k])


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
C = {}
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
Q = int(input())
for _ in range(Q):
    cost = 0
    l, r = map(int, input().split())
    i, j = C[l]
    for n in range(l + D, r + D, D):
        x, y = C[n]
        cost += abs(i - x) + abs(j - y)
        i, j = x, y
    print(cost)

Submission status: Time Limit Exceeded

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

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    ans = 0
    for q in range(qx + D, qy + D, D):
        ans += dp[q]
    print(ans)

Submission status: Time Limit Exceeded

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

H, W, D = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j] - 1] = (i, j)
        
for l, r in QL:
    ans = 0
    c = l - 1
    x, y = m[c]
    while c != r - 1:
        c += D
        nx, ny = m[c]
        
        ans += abs(x - nx) + abs(y - ny)
        x, y = nx, ny
        
    print(ans)

Submission status: Time Limit Exceeded

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

numbers = {}
for y in range(H):
	for x in range(W):
		numbers[A[y][x]] = (y, x)

for l, r in LR:
	cost = 0
	while l != r:
		f, t = numbers[l], numbers[l + D]
		cost += abs(f[0] - t[0]) + abs(f[1] - t[1])
		l += D
	print(cost)

Submission status: Time Limit Exceeded

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

q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    ans=0
    p=(lr[1]-lr[0])//d
    for j in range(p):
        ans+=abs(l[lr[0]+d*j][0]-l[lr[0]+d*(j+1)][0])+abs(l[lr[0]+d*j][1]-l[lr[0]+d*(j+1)][1])
    print(ans)

Submission status: Time Limit Exceeded

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

q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    ans=0
    p=(lr[1]-lr[0])//d
    for j in range(p):
        ans+=abs(l[lr[0]+d*j][0]-l[lr[0]+d*(j+1)][0])+abs(l[lr[0]+d*j][1]-l[lr[0]+d*(j+1)][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
	H, W, D = map(int,input().split())
	pos = [0]*(H*W+1)
	for i in range(H):
		A = list(map(int, input().split()))
		for j in range(W):
			pos[A[j]] = [i, j]
	Q = int(input())
	lr = [0]*Q
	for i in range(Q):
		lr[i] = list(map(int, input().split()))
	ans = defaultdict(int)
	for i in range(1, H*W+1-D):
		pre = i
		cur = i
		d = 0
		while cur < H*W+1:
			pre_pos = pos[pre]
			cur_pos = pos[cur]
			d += abs(pre_pos[0]-cur_pos[0])+abs(pre_pos[1]-cur_pos[1])
			ans[(i, cur)] = d
			pre = cur
			cur += D
	for i in range(Q):
		print(ans[(lr[i][0], lr[i][1])])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ans = []
for _ in range(Q):
    aaa = 0
    L,R = [int(zz) for zz in input().split()]
    bl = tmp[L-1][0]
    br = tmp[L-1][1]
    for i in range(L+D,R+1,D):
        l = tmp[i-1][0]
        r = tmp[i-1][1]
        aaa += abs(bl-l) + abs(br-r)
        bl = l
        br = r
    ans.append(aaa)

[print(i) for i in 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]] = [i+1,j+1]

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


ru = {}
for i in range(1,D+1):
    if i not in ru.keys():
        ru[i] = [0]
        c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1

for i in range(Q):
    t = LR[i][0] % D
    if t == 0:
        t = D
        print(ru[t][LR[i][1]//D-1] - ru[t][LR[i][0]//D-1])
    else:
        print(ru[t][LR[i][1]//D] - ru[t][LR[i][0]//D])

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]] = [i+1,j+1]

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


ru = {}
for i in range(1,H*W+1):
    if i not in ru.keys():
        ru[i] = [0]
        c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1




for i in range(Q):
    print(ru[LR[i][0]][(LR[i][1] - LR[i][0]) // D])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]
board_dict = {}
for i in range(H):
    tmp = [int(x) for x in input().split()]
    for j, k in enumerate(tmp):
        board_dict[k] = (i+1, j+1)
Q = int(input())
lr_list = []
for _ in range(Q):
    lr_list.append([int(x) for x in input().split()])

for l, r in lr_list:
    res = 0
    now = l
    next = now+D
    while now != r:
        now_pos = board_dict[now]
        next_pos = board_dict[next]
        res += abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        now = next
        next = now+D
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def distance(x, y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    a, q, lr = aqlr[:h * w], aqlr[h * w], aqlr[h * w + 1:]
    n = h * w
    pos = [0] * (n + 1)
    for i, _a in enumerate(a):
        pos[_a] = (i // w, i % w)
    cost = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(d + 1, n + 1):
        dis = distance(pos[i - d], pos[i])
        for j in range(i):
            if (i - j) % d == 0:
                cost[i][j] = cost[i - d][j] + dis
    ans = []
    for l, r in chunked(lr, 2):
        ans.append("%d" % cost[r][l])
    return "\n".join(ans)


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Submission status: Time Limit Exceeded

Solution code:
def loc_decide(loc, w, num):
    location = [i for i in range(len(loc)) if loc[i] == num][0]
    #print(location)
    row = location // w
    column = location % w
    return [row, column]

h, w, d = map(int, input().split())
loc = []
for _ in range(h):
    tmp = list(map(int, input().split()))
    for i in range(len(tmp)):
        loc.append(tmp[i])
n = int(input())
for _ in range(n):
    start, end = map(int, input().split())
    dist = 0
    for i in range(start, end+1, d):
        if i == start:
            prev_loc = loc_decide(loc, w, i)
        else:
            next_loc = loc_decide(loc, w, i)
            dist += (abs(next_loc[0]- prev_loc[0]) + abs(next_loc[1] - prev_loc[1]))
            prev_loc = next_loc
    print(dist)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    pdic = {}

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

    for l,r in zip(L,R):
        res = 0
        for c in range(l,r+1-D,D):
            res += abs(pdic[c][0] - pdic[c+D][0])
            res += abs(pdic[c][1] - pdic[c+D][1])
        print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [ [ int(next(tokens)) for _ in range(W) ] for _ in range(H) ]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]" 
    R = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = [0]*(H*W+1)
for i in range(H):
    a = list(map(int,input().split()))
    for j in range(W):
        A[a[j]] = (i,j)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    ans = 0
    while R > L:
        ans += abs(A[L][0]-A[L+D][0]) + abs(A[L][1]-A[L+D][1])
        L += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
       
for i in range(Q):
    tmp = 0
    now = LR[i][0]
    now_state = number_dict[now]
    
    while True:
        if now == LR[i][1]:
            break
        
        tmp += abs(number_dict[now+D][0] - now_state[0]) + abs(number_dict[now+D][1] - now_state[1])
        now = now + D
        now_state = number_dict[now]
        

            
    print(tmp)

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())
LR = [list(map(int, input().split())) for _ in range(Q)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
       
for i in range(Q):
    tmp = 0
    now = LR[i][0]
    
    while True:
        if now == LR[i][1]:
            break
        
        tmp += abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
        now = now + D
        

            
    print(tmp)

Submission status: Time Limit Exceeded

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

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = [[[0,0,0]]for _ in range(D)]
dinds = [[]for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d].append(i[0])

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum].index(i[0])+1
    r = dinds[dnum].index(i[1])+1
    print(stims[dnum][r][0]-stims[dnum][l][0])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
dli = [[] for _ in range(D)]
for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        dli[j%D].append([j,i,ind])
        dli[j%D].sort()
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = []
dinds = []
for d in dli:
    #total dist,now pos
    #inds = num
    stim = [[0,0,0]]
    inds = []
    for i in d:
        stim.append([stim[-1][0]+abs(i[1]-stim[-1][1])+abs(i[2]-stim[-1][2]),i[1],i[2]])
        inds.append(i[0])
    stims.append(stim)
    dinds.append(inds)

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum].index(i[0])+1
    r = dinds[dnum].index(i[1])+1
    print(stims[dnum][r][0]-stims[dnum][l][0])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
dli = [[] for _ in range(D)]
for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        dli[j%D].append([j,i,ind])
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = []
dinds = []
for d in dli:
    #total dist,now pos
    #inds = num
    stim = [[0,0,0]]
    inds = []
    d.sort(key=itemgetter(0))
    for i in d:
        stim.append([stim[-1][0]+abs(i[1]-stim[-1][1])+abs(i[2]-stim[-1][2]),i[1],i[2]])
        inds.append(i[0])
    stims.append(stim)
    dinds.append(inds)

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum].index(i[0])+1
    r = dinds[dnum].index(i[1])+1
    print(stims[dnum][r][0]-stims[dnum][l][0])

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())
lr = [list(map(int, input().split())) for _ in range(q)]


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

cost_sum = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(d):
    for j in range(int(math.ceil(h * w / d))):
        cost_sum[i][j] = sum(cost[i][:j])

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

    _cost_sum = cost_sum[int(l % d)]
    print(_cost_sum[int(r / d)] - _cost_sum[int(l / d)])

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())
lr = [list(map(int, input().split())) for _ in range(q)]


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

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

    _cost = cost[int(l % d)]
    print(sum(_cost[int(l / d): int(r / d)]))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    su = 0
    C = B[l:r + 1:D]
    h, w = C[0]
    for nh, nw in C[1:]:
        su += abs(nh - h) + abs(nw - w)
        h, w = nh, nw
    print(su)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    q=int(input())
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        for j in range(300*300):
            if l==r: break
            chk+=ans[l]
            l+=d
        print(chk)

if __name__=="__main__":
    sol()