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: Wrong Answer

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

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

for i in range(h):
    for j,a in enumerate(input().split()):
        board[i*w+j]=int(a)

q=int(input())


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

for i in range(d+1,h*w):
    a=h*w-i
    tmp=board.index(a)
    i=tmp//w
    j=tmp%w
    tmp=board.index(a+d)
    x=tmp//w
    y=tmp%w
    distances[a-1]=distances[a+d-1]+abs(i-x)+abs(j-y)

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

Submission status: Wrong Answer

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

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

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

magic = 0

def search(word):
    for i in range(w):
        for j in range(h):
            if a[j][i] == word:
                return j+1, i+1



for k in range(q):
    while True:
        if l[k] == r[k]:
            break
        else:
            i, j = search(l[k])
            l[k] += d
            x, y = search(l[k])

            magic += abs(x-i)+abs(y-j)
print(magic)

Submission status: Wrong Answer

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]
    literature = str(L) + " " + str(D)
    length = 0
    if L == R:
        print(0)
    elif literature in end.keys():
        print(int(end[literature]))
    else:
        Lt = L
        for j 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)
        key = str(L) + " " +str(D)
        end[key] = str(length)

Submission status: Wrong Answer

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)]
S = [0 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 + D > H * W:
			break
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		if j == R:
			break
		S[j] += ans
	print(S[L] - S[R])

Submission status: Wrong Answer

Solution code:
h, w, D = map(int, raw_input().split())

d = dict()
for i in xrange(h):
    j = 0
    for n in map(int, raw_input().split()):
        d[n] = (i+1, j+1)
        j += 1

d2 = dict()
d3 = dict()
for i in xrange(input()):
    l, r = map(int, raw_input().split())
    l2 = l
    ans = 0
    if l in d3:
        if d3[l][0] <= r:
            ans = d3[l][1]
            l = d3[l][0]
    px, py = d[l]
    while l <= r:
        if "%d,%d" % (l, r) in d2:
            ans += d2["%d,%d" % (l, r)]
            d2["%d,%d" % (l2, r)] = ans
            break
        x, y = d[l]
        ans += abs(px-x)+abs(py-y)
        px = x
        py = y
        l += D
    d2["%d,%d" % (l2, r)] = ans
    d3[l2] = (r, ans)
    print ans

Submission status: Wrong Answer

Solution code:
hwd = list(map(int,input().split()))
a = [ None for x in range(hwd[0])]

idx_dic = {}

for i in range(hwd[0]):
    a = list(map(int,input().split()))
    for j in range(hwd[1]):
        idx_dic[a[j]] = (i,j)
    
q = int(input())
lr = [None for x in range(q)]
move_list = [[] for x in range(q)]

for i in range(q):
    lr[i] = list(map(int,input().split()))
    l = lr[i][0]
    move_list[i].append(l)
    while(1):
        if l == lr[i][1]:
            move_list[i].append(lr[i][1])
            break
        else:
            l += hwd[2]
            move_list[i].append(l)

def telepoto(idx_dic,move_list):
    distance = 0
    for i in range(len(move_list)):
        current_ml = move_list[i]
        for j in range(len(current_ml)-1):
            # x,y to X,Y
            x,y = idx_dic[current_ml[j]]
            X,Y = idx_dic[current_ml[j+1]]
            distance += abs(x-X) + abs(y-Y)
    return distance

ans = telepoto(idx_dic,move_list)
print(ans)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j,a in enumerate(input().split()):
        print(i*w+j,i,j)
        board[i*w+j]=int(a)

q=int(input())


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

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


    res=0
    while(l!=r):
        if distances[l]==-1:
            tmp=board.index(l)
            i=tmp//w
            j=tmp%w
            tmp=board.index(l+d)
            x=tmp//w
            y=tmp%w
            distances[l]=abs(i-x)+abs(j-y)
        res+=distances[l]
        l+=d
    print(res)

Submission status: Wrong Answer

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)]
S = [0 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
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		if j == R:
			break
			
		S[j] += ans
	print (ans)

Submission status: Wrong Answer

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

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

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

dic = [0] * (h * w)

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

q = int(input())

dic2 = {}
for i in range(q):
    l, r = map(int, input().split())
    
    if (l, r) in dic2:
        print(l, r)
        continue
    
    ans = 0
    c = l
    while c != r:
        y, x = dic[c - 1]
        ny, nx = dic[c + d - 1]
        
        ans += abs(ny - y) + abs(nx - x)
        c += d
        
        dic2[(l, c)] = ans
        
    print(ans)

Submission status: Wrong Answer

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()))
    coordinates = np.zeros([H*W+1, 2], dtype=int)
    for i in range(H):
        line = list(map(int, input().split()))
        for j, x in enumerate(line):
            coordinates[x] = i, j


    # 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)])

    # coordinates = np.array([np.where(board == i+1) for i in range(H*W)]).reshape(H*W, 2)
    # coordinates = np.array([np.array(np.where(board == i+1)).reshape(-1) for i in range(H*W)])
    x_coordinates, y_coordinates = np.split(coordinates, 2, axis=1)
    # print(coordinates)

    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)
        xs = x_coordinates[nums]
        ys = y_coordinates[nums]
        # print(nums, xs, ys)

        ans = np.sum(np.abs(xs[1:] - xs[:-1])) + np.sum(np.abs(ys[1:] - ys[:-1]))
        print(ans)

        memo[(L, R)] = ans

Submission status: Wrong Answer

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)]
S = [0 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
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		S[j] += ans
	print (ans)

Submission status: Wrong Answer

Solution code:
#
H, W, D = list(map(int, input().split()))
A = {}
for y in range(H):
    tmp = list(map(int, input().split()))
    for x in range(W):
        A[tmp[x]] = (x+1, y+1)
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)


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

    if (L, R) in prev:
        print(prev[(L, R)])
        continue

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

    for i in range((R-L)//D):
        L += D
        s, t = A[L]#get_pos(L)
        magic += abs(x-s) + abs(y-t)
        x = s
        y = t

    print(magic)
    prev[(L, R)] = magic

Submission status: Wrong Answer

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)]
S = [0 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
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		S[j] += ans
	print (ans)

Submission status: Wrong Answer

Solution code:
s = input().split()

H = int(s[0])
W = int(s[1])
D = int(s[2])

d = {}

for i in range(1, H+1):
    s = input().split()
    for j in range(W):
        d[int(s[j])] = (i, j+1)

Q = int(input())

score = {}

for i in range(Q):
    mp = 0
    lr = input().split()
    L = int(lr[0])
    R = int(lr[1])
    if score.get((L,R), None) is not None:
        print(score[(L,R)])
        continue
    while L != R:
        buffer = d[L]
        L += D
        mp += abs(d[L][0]-buffer[0])+abs(d[L][1]-buffer[1])
    score[(L,R)] = mp
    print(mp)

Submission status: Wrong Answer

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)

    from collections import defaultdict
    memo = defaultdict(int)

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

            # 履歴があれば使う
            ans_histo = memo[(fr, to)]
            if ans_histo > 0:
                sum_magic += ans_histo
                break

            # なければ計算
            frx, fry = a[fr]
            tox, toy = a[to]
            dist = abs(frx-tox) + abs(fry-toy)
            # print(mi, fr, to, dist)

            # メモ
            memo[(fr, to)] = dist

            sum_magic += dist

        print(sum_magic)

solve()

Submission status: Wrong Answer

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)]
S = [0 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
		if S[j]:
			ans += S[j]
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		S[j] += ans
	print (ans)

Submission status: Wrong Answer

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]
    literature = str(L) + " " + str(D)
    length = 0
    if L == R:
        print(0)
    elif literature in end.keys():
        print(int(end[literature]))
    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)
        key = str(L) + " " +str(D)
        end[key] = str(length)

Submission status: Wrong Answer

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())
    
d={}
    
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]):
        if(x in d):
            MP+=d[x][0]
            Px=d[x][1]
            Py=d[x][2]
            x+=D
        else:
            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)
                    d[x-D]=[MP,Pnx,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: Wrong Answer

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):
    lut = dict()
    for l, r in queries:
        ss = '{:03d}{:03d}'.format(l, r)
        if ss in lut:
            ans = lut[ss]
            print(ans)
            break
        ans = 0
        while True:
            if l == r:
                break
            res = sub_solve(l, l+D)
            ans += res
            l += D
        print(ans)
        lut[ss] = 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: Wrong Answer

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

rec = {}
Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    num = 0
    while L != R:
        if (L, R) in rec:
            num += rec[(L, R)]
            break
        else:
            p = abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
            rec[(L, R)] = p
            num += p
        L += D
    print(num)

Submission status: Wrong Answer

Solution code:
#
H, W, D = list(map(int, input().split()))
A = {}
for y in range(H):
    tmp = list(map(int, input().split()))
    for x in range(W):
        A[tmp[x]] = (x+1, y+1)
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)


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

    if (L, R) in prev:
        print(prev[(L, R)])
        continue

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

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

    print(magic)
    prev[(L, R)] = magic

Submission status: Wrong Answer

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

AhD = np.array([0]*(H*W))
AwD = 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

for i in range(H*W):
    ah = Ah[0:i+1][::D]
    AhD[i] = np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[0:i+1][::D]
    AwD[i] = np.sum(np.abs(aw[1:] - aw[0:-1]))


Q = int(raw_input())

def solve(l, r):
    ans = 0
    ans = AhD[r-1] - AhD[l-1] + AwD[r-1] - AwD[l-1]
    # 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: Wrong Answer

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
ansmemo = [0] * 90001
for i in range(0, times):
    temp = list(map(int, input().split(" ")))
    nowloc = temp[0]
    ans = 0
    if ansmemo[temp[0]] == 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]
        ansmemo[temp[0]] = ans
    print(ans)

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
A = []
C = [0 for _ in range(H * W + 1)]
for h in range(H):
    A.append(list(map(int, input().split())))
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
h = [0 for _ in range(H * W + 1)]
for i in range(D):
    s = 0
    for j in range(i, H * W, D):
        if j != i:
            print(j)
            n = (C[j + 1][0], C[j + 1][1])
            p = (C[j + 1 - D][0], C[j + 1 - D][1])
            s += abs(n[0] - p[0]) + abs(n[1] - p[1])
        h[j + 1] = s
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(h[r] - h[l])

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
A = []
C = [0 for _ in range(H * W + 1)]
for h in range(H):
    A.append(list(map(int, input().split())))
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
print(A)
print(C)
h = [0 for _ in range(H * W + 1)]
for i in range(D):
    s = 0
    for j in range(i, H * W, D):
        if j != i:
            print(j)
            n = (C[j + 1][0], C[j + 1][1])
            p = (C[j + 1 - D][0], C[j + 1 - D][1])
            s += abs(n[0] - p[0]) + abs(n[1] - p[1])
        h[j + 1] = s
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(h[r] - h[l])

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w, d = na()
a = []
for i in range(h):
    a.append(na())

wh = [None] * (h*w)
for i in range(h):
    for j in range(w):
        wh[a[i][j]-1] = (i,j)

xs = []
for i in range(d):
    row = [0]
    for j in range(i+d, h*w, d):
        row.append(row[-1] +
                   abs(wh[j][0]-wh[j-d][0]) +
                   abs(wh[j][1]-wh[j-d][1]))
    xs.append(row)

q = ni()
for z in range(q):
    l, r = na()
    l -= 1; r -= 1
    print(xs[l%d][r//d-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)]
b = [0]*(h*w+1)
for i in range(h):
  for j in range(w):
    b[a[i][j]] = (i,j)
for l,r in lr:
  ans = 0
  while(l!=r):
    i,j = b[l]
    l += d
    x,y = b[l]
    ans += abs(x-i)+abs(y-j)
    x += 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)]

x = [0]*(H*W+1)

for h1 in range(H):
    for w1 in range(W):
        if A[h1][w1] > H*W-D:
            continue
        f = False
        for h2 in range(H):
            for w2 in range(W):
                if A[h1][w1]+D == A[h2][w2]:
                    x[A[h2][w2]] = abs(h1-h2)+abs(w1-w2)
                    f = True
                    break
            if f:
                break

y = x[:D+1]
for i in range(D+1, H*W+1):
    y.append(y[i-D]+x[i])

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
for _ in range(Q):
    ans = 0
    l, r = na()
    t = (r - l) // D
    for j in range(t):
        px, py = d[l + j * D]
        nx, ny = d[l + (j + 1) * D]
        #print(px, py, nx, ny)
        ans += abs(px - nx) + abs(py - ny)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
A = np.array(A)
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
for _ in range(Q):
    ans = 0
    l, r = na()
    t = (r - l) // D
    for j in range(t):
        px, py = d[l + j * D]
        nx, ny = d[l + (j + 1) * D]
        #print(px, py, nx, ny)
        ans += abs(px - nx) + abs(py - 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)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[0]*(h*w + 1) for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    while now + d <= h*w:
        s_d[i][now + d] = s_d[i][now] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1])
        now += d
#print(s_d)


def query(l, r):
    idx = l % d
    if idx == 0:
        idx = d
    cost = s_d[idx][r] - s_d[idx][l]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(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)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)


def query(l, r):
    cost = 0
    now = iti[l]
    while l < r:
        next = iti[l + d]
        cost += abs(now[0] - next[0]) + abs(now[1] - next[1])
        l += d
        now = iti[l]
    return cost


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, i8

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

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

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

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


@njit
def solve(h, w, d, arr):
    result = [[0] for _ in range(d)]
    for i in range(d):
        l = i
        score = 0
        while l + d <= h * w:
            if l == 0:
                result[i].append(score)
                l += d
                continue
            u = np.where(arr == l)
            v = np.where(arr == l + d)
            score += abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0])
            result[i].append(score)
            l += d
    return result


result = solve(h, w, d, arr)


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

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline

  H,W,D=map(int,pin().split())
  d=[[0,0]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]
  e=[0]*(H*W)
  Q=int(pin())
  for _ in [0]*Q:
    k=pin().split()
    L=int(k[0])
    R=int(k[1])
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      if e[s]==0:
        g=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
        e[s]=g
        ans+=g
      else:
        ans+=e[s]
      h+=D
      
    print(ans)
  return
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

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

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

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


result = defaultdict(list)
for i in range(d):
    result[i].append(0)

for i in range(d):
    l = i
    score = 0
    while l + d <= h * w:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        u = np.where(arr == l)
        v = np.where(arr == l + d)
        score += abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0])
        result[i].append(score)
        l += d

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

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline

  H,W,D=map(int,pin().split())
  d=[[0,0]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())
  for _ in [0]*Q:
    k=pin().split()
    L=int(k[0])
    R=int(k[1])
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=D
    print(ans)
  return
main()

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[0,0]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())
  u=H*W
  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=D
    print(ans)
  return
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

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

q=int(input())
for i in range(q):
  l,r=nii()
  ans=0
  cy,cx=a_dict[l]
  while l!=r:
    l+=d
    ny,nx=a_dict[l]
    ans+=abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

  print(ans)