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: Accepted

Solution code:
str1 = input().split(" ")
h = int(str1[0])
w = int(str1[1])
d = int(str1[2])
res = [0 for i in range(90001)]
px = [0 for i in range(90001)]
py = [0 for j in range(90001)]
for i in range(h):
    str2 = input().split(" ")
    for j in range(w):
        px[int(str2[j])] = i
        py[int(str2[j])] = j

for i in range(d+1, h*w+1):
    res[i] = res[i - d] + abs(px[i] - px[i - d]) + abs(py[i] - py[i - d])
q = int(input())
for i in range(q):
    str3 = input().split(" ")
    print(res[int(str3[1])] - res[int(str3[0])])

Submission status: Accepted

Solution code:
# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])

Submission status: Accepted

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

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

xx = [0 for i in range(90002)]
yy = [0 for i in range(90002)]
for y in range(H):
    for x in range(W):
        xx[Amap[y][x]] = x
        yy[Amap[y][x]] = y
Q = int(input())

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

# magic point calculation
mp = [0 for i in range(90002)]

for i in range(D+1, 90002):
    mp[i] = mp[i-D] + abs(xx[i] -xx[i-D]) + abs(yy[i] - yy[i-D])

for i in coord:
    print(mp[i[1]] - mp[i[0]])

Submission status: Accepted

Solution code:
H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [0] * (H * W + 1)
for i in range(D):
    x = H * W - i - D
    r = 0
    while x > 0:
        table[x] = abs(A[x][0] - A[x+D][0]) + abs(A[x][1] - A[x+D][1]) \
                   + r
        r = table[x]
        x -= D
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    print(table[l] - table[r])

Submission status: Accepted

Solution code:
H, W, D = [int(i) for i in input().split()]
px = [0] * 90001
py = [0] * 90001

for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        px[v] = j
        py[v] = i

d = [0] * 90001
for i in range(D + 1, 90001):
    d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])

Q = int(input())

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

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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

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

Q = int(input())
LR = []
for _ in range(Q):
    LR.append(tuple([int(n) for n in input().split()]))

P = defaultdict(lambda: (0, 0))
for i, j in itertools.product(range(H), range(W)):
    P[A[i][j]] = (i + 1, j + 1)

DD = defaultdict(int)
for i in range(D + 1, H * W + 1):
    DD[i] = DD[i - D] + abs(P[i][0] - P[i - D][0]) + abs(P[i][1] - P[i - D][1])

for l, r in LR:
    print(DD[r] - DD[l])

Submission status: Accepted

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

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

m = [0 for _ in range(h*w + 1)]
acm = [0 for _ in range(h*w + 1)]
ans = []

for i in range(h):
    a = [int(x) for x in input().split()]
    for j,k in enumerate(a):
        m[k] = (i,j)

for i in range(1, d+1):
    count = i
    while count <= h * w:
        if count <= d:
            pass
        else:
            acm[count] = dist(m[count],m[count-d]) + acm[count-d]
        count += d

q = int(input())

for i in range(q):
    l,r = map(int, input().split())
    ans.append(acm[r] - acm[l])

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

def manhattan(y1, x1, y2, x2): return abs(y1 - y2) + abs(x1 - x2)


def solve(H, W, D, A, query):
    num_pos = dict()
    for y in range(H):
        for x in range(W):
            num_pos[A[y][x]] = (y, x)

    dp = [None] * (H * W + 1)
    for i in range(1, D + 1):
        dp[i] = 0
        for j in range(i + D, len(dp), D):
            y1, x1 = num_pos[j - D]
            y2, x2 = num_pos[j]
            dp[j] = dp[j - D] + manhattan(y1, x1, y2, x2)

    for q in query:
        L, R = q
        print(dp[R] - dp[L])


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

    solve(H, W, D, A, query)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import numpy as np

def diff(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

H, W, D = map(int, input().split())
pos = dict()
for i in range(H):
    buf = list(map(int, input().split()))
    for j in range(W):
        pos[buf[j]] = (i, j)
        
Q = int(input())
query = []
for _ in range(Q):
    l, r = map(int, input().split())
    query.append((l, r))
        
cost = np.zeros(H * W + 1).astype(int)
for i in range(1, D + 1):
    cost[i] = 0
    x = i + D
    while x <= H * W:
        cost[x] = cost[x - D] + diff(pos[x - D], pos[x])
        x += D
        
for l, r in query:
    print(cost[r] - cost[l])

Submission status: Accepted

Solution code:
H,W,D = list(map(int, input().split()))
X = [[0,0] for i in range(H*W+1)]

for i in range(1, H+1):
	A = list(map(int, input().split()))
	for idx, a in enumerate(A):
		X[a] = [i, idx+1]

Q = int(input())
L = []
R = []
S = [0]*(H*W+1)

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

for i in range(D+1, H*W+1):
	S[i] = S[i-D] + abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])

for i in range(Q):
	print(S[R[i]] - S[L[i]])

Submission status: Accepted

Solution code:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])

Submission status: Accepted

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

I = [0] * (w * h + 1)
for i in range(h):
    for j in range(w):
        I[A[i][j]] = (i, j)
D = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    D[i] = D[i - d] + abs(I[i][0] - I[i - d][0]) + abs(I[i][1] - I[i - d][1])
s = []
g = []
for i in range(q):
    s, g = map(int, input().split())
    print(D[g] - D[s])

Submission status: Accepted

Solution code:
H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
L=[]
R=[]
S=[0]*(H*W+1)

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

for i in range(D+1,H*W+1):
	S[i]=S[i-D]+abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])

for i in range(Q):
	print(S[R[i]]-S[L[i]])

Submission status: Accepted

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

if __name__ == "__main__":
	H, W, D = list(map(int, input().split()))
	masu = {}
	for i in range(H):
		inputs = list(map(int, input().split()))
		for j in range(W):
			masu[inputs[j]] = [i, j]

	Q = int(input())
	L = []
	R = []
	for i in range(Q):
		l, r = list(map(int, input().split()))
		L.append(l)
		R.append(r)
	# i=D+1 ~ H*W の累積和Sを求める
	S = [0] * (H*W+1)
	for i in range(D+1, H*W+1):
		S[i] = S[i-D] + abs(masu[i][0]-masu[i-D][0]) + abs(masu[i][1]-masu[i-D][1])
	# 回答する
	for i in range(Q):
		print(S[R[i]] - S[L[i]])

Submission status: Accepted

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))

Submission status: Accepted

Solution code:
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])

Submission status: Accepted

Solution code:
H, W, D = [int(x) for x in input().split()]
size = H*W+1
c = [(-1, -1)] * size
p = [0] * size

for y in range(H):
    for x, a in enumerate([int(s) for s in input().split()]):
        c[a] = (x, y)

for a in range(D+1, size):
    p[a] = p[a-D] + abs(c[a][0] - c[a-D][0]) + abs(c[a][1] - c[a-D][1])

Q = int(input())
for i in range(Q):
    L, R = [int(lr) for lr in input().split()]
    print(p[R] - p[L])

Submission status: Accepted

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

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

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

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


    pre = [[0 for j in range((2*H*W)//D)  ] for i in range(D)]
    for i in range(D,H*W):
        pre[i%D][i//D] = pre[i%D][i//D - 1] + dist(pos[i], pos[i-D])

    Q = int(input())
    for _ in range(Q):
        L,R = map(int,input().split())
        L -= 1
        R -= 1

        v = pre[L%D]
        print(v[R//D] - v[L//D])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in xrange(h)]
r = {a[x][y]: (x, y) for x in xrange(h) for y in xrange(w)}
b = [0] * (h * w + 1)
for _ in xrange(d + 1, h * w + 1):
    b[_] = b[_ - d] + sum([abs(r[_ - d][i] - r[_][i]) for i in [0, 1]])
for _ in xrange(input()):
    l, r = map(int, raw_input().split())
    print b[r] - b[l]

Submission status: Accepted

Solution code:
def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        print(s,t)
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, D+1)])
for d in range(D+1, H*W+1):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)

Submission status: Accepted

Solution code:
def get_next_int():
    return int(float(input()))
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    h, w, d = get_next_ints()
    values = {}
    for i in range(h):
        line_data = get_next_ints()
        for j, a in enumerate(line_data):
            values[a] = (i, j)
    from collections import defaultdict
    distances = defaultdict(int)
    
    for a in range(1,h * w + 1):
        i, j = values[a]
        prev = a - d
        if prev in values:
            prev_i, prev_j = values[prev]
            distances[a] = abs(prev_i - i) + abs(prev_j - j) + distances[prev]
        else:
            distances[a] = 0
    q = get_next_int()
    for k in range(q):
        r, l = get_next_ints()
        print(distances[l] - distances[r] )
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Submission status: Accepted

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

    grid = dict()
    for i, a in enumerate(A):
        for j, b in enumerate(a):
            grid[b] = (i + 1, j + 1)

    l = H * W
    dist = [0] * (l + 1)
    for i in range(l, 0, -1):
        if i + D <= l:
            dist[i] = abs(grid[i][0] - grid[i+D][0]) + abs(grid[i][1] - grid[i+D][1]) + dist[i+D]
        else:
            dist[i] = 0

    for l, r in LR:
        print(dist[l] - dist[r])

main()

Submission status: Accepted

Solution code:
H,W,D=map(int,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1

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

for i in range(1,H*W+1):
	if i<=D:
		continue
	dist[i]=dist[i-D]+abs(C[i-D][0]-C[i][0])+abs(C[i-D][1]-C[i][1])
	

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

Submission status: Accepted

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

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

dic = [0] * (h * w)

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

s = [[0] * (h * w // d + (i < h * w % d)) for i in range(d)]

for i in range(d):
    for j in range(1, len(s[i])):
        b = i + d * (j - 1)
        c = i + d * j

        y, x = dic[b]
        ny, nx = dic[c]
        s[i][j] = s[i][j - 1] + abs(ny - y) + abs(nx - x)

q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(s[l % d][r // d] - s[l % d][l // d])

Submission status: Accepted

Solution code:
def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def main():
    H,W,D = map(int,input().split())
    index  = [(0,0) for i in range(H*W+1)]
    A = []
    for i in range(H):
        temp = list(map(int, input().split()))
        for t in temp:
            index[t] = (i,temp.index(t))
        A.append(temp)
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    dp = [0 for i in range(H*W+1)]
    for i in range(D, H*W+1):
        dp[i] = dp[i-D] + calc(index[i], index[i-D])
    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        print(dp[R]-dp[L])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
        
power_accumulation = []
for i in range(hwd[2]):
    power = [0]
    number = 0
    place = i
    while place < hwd[0] * hwd[1] - hwd[2]:
        power.append(power[number] + abs(xy[place + hwd[2]][0] - xy[place][0]) + abs(xy[place + hwd[2]][1] - xy[place][1]))
        number = number + 1
        place = place + hwd[2]
    power_accumulation.append(power)

for i in range(q):
    test_power = power_accumulation[(lr[i][1] - 1) % hwd[2]][(lr[i][1] - 1) // hwd[2]] - power_accumulation[(lr[i][0]- 1) % hwd[2]][(lr[i][0] - 1) // hwd[2]]
    print(test_power)

Submission status: Accepted

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

#
d = [0 for _ in range(H*W)]
for i in range(1, D+1):
    x, y = A[i]

    j = i
    while j+D<=H*W:
        s, t = A[j+D]
        d[j+D-1] = d[j-1] + abs(x-s) + abs(y-t)
        x = s
        y = t
        j += D

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

    print(d[R-1] - d[L-1])

Submission status: Accepted

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

h,w,d=map(int,input().split())
table=[]
cost=[[0 for i in range(w)] for j in range(h)]
dic={}
for i in range(h):
    t=list(map(int,input().split()))
    table.append(t)
    for j in range(w):
        dic[t[j]]=(i,j)

for i in range(1,h*w+1):
    now=i
    a,b=dic[now]
    if cost[a][b]==0:
        while now<=h*w-d:
            now+=d
            y,x=dic[now]
            if cost[y][x]!=0:
                break
            cost[y][x]+=cost[a][b]+dist((a,b),(y,x))
            a,b=y,x

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    a,b=dic[l]
    c,d=dic[r]
    print(cost[c][d]-cost[a][b])

Submission status: Accepted

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

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

for l, r in lr:
    print(dp[r] - dp[l])

Submission status: Accepted

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]

memo = [0] * 90001

for i in range(1, a[0] * a[1]+1):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

Submission status: Accepted

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

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

MP = [0 for _ in range(H*W)]
for i in range(H*W):
    if i < D:
        MP[i] = 0
    else:
        MP[i] = MP[i-D] + abs(masu[i][0]-masu[i-D][0]) + abs(masu[i][1]-masu[i-D][1])

for i in range(Q):
    print(MP[R[i]-1] - MP[L[i]-1])

Submission status: Accepted

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

Amap = {A[i][j]: (i, j) for i in range(H) for j in range(W)}


def move_mp(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])


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

for i in range(D + 1, H * W + 1):
    mp_list[i] = mp_list[i - D] + move_mp(Amap[i - D], Amap[i])

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

    print(mp_list[R] - mp_list[L])

Submission status: Accepted

Solution code:
H, W, D = list(map(int, input().split()))
 
dic = {}
for i in range(H):
    for j,v in enumerate(list(map(int, input().split()))):
        dic[v] = (i,j)
 
Q = int(input())
 
Qs = []
mi = 100000
ma = 1
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)
    ma = max(ma, r)
 
S = [0 for i in range(100000)]
acm = 0
pi, pj = dic[mi]
for start in range(1, D+1):
    for i in range(start, ma+1, D):
        x,y = dic[i]
        acm += abs(x-pi) + abs(y-pj)
        S[i] = acm
        pi,pj = x,y

for i in Qs:
    l,r = i
    print(S[r] - S[l])

Submission status: Accepted

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

    pos = [0] * (H * W + 1)
    for i, row in enumerate(A):
        for j, value in enumerate(row):
            pos[value] = (i, j)

    d = [0] * (H * W + 1)
    for x in range(D + 1, H * W + 1):
        y = x - D
        p1, p2 = pos[x], pos[y]
        d[x] = d[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

    for l, r in ST:
        print(d[r] - d[l])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*(H*W+1)
for i in range(D+1,H*W+1):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
pos = {a[i][j]: (i,j) for i in range(h) for j in range(w)}
acc = [0]*(h*w+1)
for v in range(d+1, h*w+1):
    i, j = pos[v]
    x, y = pos[v-d]
    acc[v] = acc[v-d] + abs(x-i) + abs(y-j)
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(acc[r] - acc[l])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [[int(i) for i in input().split()]for i in range(H)]
Q = int(input())
L = [0 for i in range(Q)]
R = [0 for i in range(Q)]
for i in range(Q):
    L[i], R[i] = map(int, input().split())
B = [(0,0) for i in range(H*W)]
for i in range(H):
    for j in range(W):
        B[A[i][j]-1] = (i,j)
C = [0 for i in range(H*W)]
for k in range(H*W):
    if k-D<0:
        C[k] = 0
    else:
        C[k] = C[k-D] + abs(B[k][0]-B[k-D][0])+abs(B[k][1]-B[k-D][1])
for n in range(Q):
    print(C[R[n]-1]-C[L[n]-1])

Submission status: Accepted

Solution code:
import numpy as np

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = np.zeros([H * W + 1]).astype(np.int)
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])

Submission status: Accepted

Solution code:
# 解説を見て                                                     
def input_to_int_list(input_str):
    return list(map(lambda x: int(x), input_str.split(' ')))


h, w, d = input_to_int_list(input())
x_ix = [0 for _ in range(h * w + 1)] 
y_ix = [0 for _ in range(h * w + 1)] 

for i in range(h):
    input_list = input_to_int_list(input())
    for j in range(w):
        v = input_list[j]
        x_ix[v] = i 
        y_ix[v] = j 

cost_list = [0 for _ in range(h * w + 1)] 
for i in range(d + 1, h * w + 1): 
    cost_list[i] = cost_list[i - d] \
                    + abs(x_ix[i] - x_ix[i - d]) \
                    + abs(y_ix[i] - y_ix[i - d]) 

q = int(input())
for i in range(q):
    input_list = input_to_int_list(input())
    l = input_list[0]
    r = input_list[1]
    print(cost_list[r] - cost_list[l])

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])

Submission status: Accepted

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

coords = [[0,0] for x in range(H*W)]
for i in range(H):
    row = input().split()
    for j in range(W):
        coords[int(row[j]) - 1] = [i,j]

dp = [[] for x in range(D)]
for i in range(D):
    temp = i
    while temp < H*W:
        if temp == i:
            dp[i].append(0)
        else:
            a = len(dp[i])
            dp[i].append(dp[i][a - 1] + abs(coords[temp][0] - coords[temp - D][0]) + abs(coords[temp][1] - coords[temp - D][1]))
        temp += D

Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    L -= 1
    R -= 1
    print(dp[R%D][R//D] - dp[L%D][L//D])

Submission status: Accepted

Solution code:
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

nDis = [0 for i in range(nS + 1)]

for i in range(nS + 1):
    nDis[i] = 0
    if i <= nD:
        continue
    
    nTmpDis = nDataH[i] - nDataH[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nTmpDis = nDataW[i] - nDataW[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nDis[i] += nDis[i - nD]

for i in range(nQ):
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    Ans = nDis[nR] - nDis[nL]
    print(Ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    h, w, d = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(h)]

    # f => (y, x) mapping
    c_map = [0] * (h * w)
    for y in range(h):
        for x in range(w):
            c_map[f[y][x] - 1] = (y, x)

    # cost accumulation
    d_map = [0] * (h * w)
    for i in range(d, h * w):
        y, x = c_map[i]
        y2, x2 = c_map[i - d]
        d_map[i] = d_map[i - d] + abs(y2 - y) + abs(x2 - x)

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

    print("\n".join(map(str, results)))