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:
import sys
input = sys.stdin.readline


h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

xy = {}
for x, ai in enumerate(a):
    for y, aij in enumerate(ai):
        xy[aij] = (x, y)

acc = [[0] for _ in range(d)]
for num in range(d + 1, h * w + 1):
    (x, y), (i, j) = xy[num - d], xy[num]
    cost = abs(x - i) + abs(y - j)
    acc[num % d].append(acc[num % d][-1] + cost)

for l, r in lr:
    ans = acc[r % d][(r - 1) // d] - acc[l % d][(l - 1) // d]
    print(ans)

Submission status: Accepted

Solution code:
import itertools
I = [int(_) for _ in open(0).read().split()]
H, W, D = I[:3]
A = I[3:3 + H * W]
Q = I[3 + H * W]
LR = I[4 + H * W:]

a_i = [0] * (H * W + 1)
for i, a in enumerate(A):
    a_i[a] = i


def calc(a1):
    a2 = a1 + D
    hw1 = a_i[a1]
    h1, w1 = divmod(hw1, W)
    hw2 = a_i[a2]
    h2, w2 = divmod(hw2, W)
    return abs(h2 - h1) + abs(w2 - w1)


score = [0] + [calc(i) for i in range(1, H * W + 1 - D)]
cum = [[0] + list(itertools.accumulate(score[i::D])) for i in range(D)]
ans = []
for l, r in zip(LR[::2], LR[1::2]):
    ans += [cum[r % D][r // D] - cum[l % D][l // D]]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

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

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

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        ans[i] = csum[r] - csum[l]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, D = map(int, readline().split())
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q, *LR = map(int, read().split())

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)
    vec[0] = vec[D]

    csum = [0] * D
    for i in range(D):
        N = (H * W - i) // D + 1
        csum[i] = [0] * N
        for j in range(N - 1):
            csum[i][j + 1] = (
                csum[i][j]
                + abs(vec[i + (j + 1) * D][0] - vec[i + j * D][0])
                + abs(vec[i + (j + 1) * D][1] - vec[i + j * D][1])
            )

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        n, m = divmod(l, D)
        ans[i] = csum[m][(r - l) // D + n] - csum[m][n]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def manhattan(p0, p1):
    return abs(p0[0]-p1[0])+abs(p0[1]-p1[1])


def solve():
    """
    """
    H, W, D = read_ints()
    arr = [None for _ in range(H*W)]
    for i in range(H):
        for j, a in enumerate(read_ints()):
            arr[a-1] = (i, j)
    prefix = [0]*(H*W)
    for i in range(D):
        for j in range(i+D, H*W, D):
            prefix[j] = prefix[j-D]+manhattan(arr[j], arr[j-D])
    Q = read_int()
    for _ in range(Q):
        l, r = read_ints()
        print(prefix[r-1]-prefix[l-1])




if __name__ == '__main__':
    solve()

Submission status: Accepted

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


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

table = {}

for i in range(h):
    a = list(map(int, input().split()))
    for j in range(w):
        table[a[j]] = (j + 1, i + 1)

cum = [0] * (h * w + 1)
for i in range(h * w + 1):
    if i > d:
        cum[i] = cum[i - d] + dist(table[i], table[i - d])


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

Submission status: Accepted

Solution code:
def main():
    h, w, d = map(int, input().split())
    ans = [[0] for _ in range(d)]
    s = [0] * d
    ans[0].append(0)
    dict = {}
    for i in range(h):
        for j, a in enumerate(list(map(int, input().split()))):
            dict[a] = (i, j)
    for i in range(1, h * w + 1 - d):
        m = i % d
        s[m] += abs(dict[i][0] - dict[i + d][0]) + abs(dict[i][1] - dict[i + d][1])
        ans[m].append(s[m])
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        m = l % d
        print(ans[m][r // d] - ans[m][l // d])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    a = [None] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = (i, j)

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        xb, yb = a[i-d]
        xn, yn = a[i]
        c[i] = c[i - d] + abs(xn - xb) + abs(yn - yb)

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

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

    dist = [0] * (w * h + 1)

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

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

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

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

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

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = [int(x) for x in input().strip().split()]
    M = [0] * H
    C = {}
    revM = {}
    for h in range(H):
        M[h] = [int(x) for x in input().strip().split()]
        for i, w in enumerate(M[h]):
            revM[w] = (h, i)
    Q = int(input())
    HW = H * W
    ans = [0] * (HW + 1)
    for i in range(1, D+1):
        cur = i
        while cur + D <= HW:
            ans[cur+D] += ans[cur] + abs(revM[cur][0] - revM[cur+D][0]) + abs(revM[cur][1] - revM[cur+D][1])
            cur += D

    for q in range(Q):
        l, r = [int(x) for x in input().strip().split()]
        print(ans[r]-ans[l])

if __name__ == '__main__':
    main()

Submission status: Accepted

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)
#print(b)
ans = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    ans[i] = ans[i-d]+abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
#print(ans)
for i in range(q):
    x,y = lr[i][0],lr[i][1]
    print(ans[y]-ans[x])

Submission status: Accepted

Solution code:
import collections
h,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(h)]
coord,cost = {mat[i][j]:(i,j) for i in range(len(mat)) for j in range(len(mat[0]))}, collections.Counter()
def f(uu,vv): 
	return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1, h * w + 1):
	if u - d >= 1: cost[u] = f(coord[u], coord[u - d]) + cost[u - d]
for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print cost[v] - cost[u]

Submission status: Accepted

Solution code:
H,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(H)]

h = {}
cost = {}
for i in range(len(mat)):
	for j in range(len(mat[0])):
		h[mat[i][j]] = (i,j)

import collections
cost = collections.Counter()
def f(uu,vv): return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1,H*w + 1):
	if u - d >= 1: cost[u] = f(h[u], h[u - d]) + cost[u - d]


def g(u,v, cost,d): return cost[v] - cost[u]# if  in cost else 0) 

for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print g(u,v,cost, d)

Submission status: Accepted

Solution code:
H,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(H)]

h = {}
cost = {}
for i in range(len(mat)):
	for j in range(len(mat[0])):
		h[mat[i][j]] = (i,j)

cost = {}
def f(uu,vv): return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1,H*w + 1):
	if u - d >= 1:
		cost[u] = f(h[u], h[u - d]) + cost[u - d]
	else:
		cost[u] = 0 

def g(u,v, cost,d):
	p = u
	return cost[v] - (cost[p] if p in cost else 0) 

for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print g(u,v,cost, d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    H, W, D = map(int, input().split())
    A = [None] * (H*W)
    for i in range(H):
        s = list(map(int, input().split()))
        for j in range(W):
            A[s[j]-1] = (i,j)

    # print(A)
    costs = [0]*(H*W)
    for i in range(D):
        j = H*W-1-i
        while j-D >= 0:
            costs[j-D] = costs[j] + abs(A[j][0]-A[j-D][0]) + abs(A[j][1]-A[j-D][1])
            j -= D
    
    Q = int(input())
    for i in range(Q):
        L, R = map(lambda x: int(x)-1, input().split())
        print(costs[L]-costs[R])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, D = list(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)]

d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)
    p.append(q)


for l, r in LR:
    i = l % D - 1
    s = (l - 1) // D
    e = (r - 1) // D
    print(p[i][e] - p[i][s])

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, D = list(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)]

# 1 -> 1+D ->
# 2 -> 2+D ->
# 3 -> 3+D -> みたいなものを事前に計算

# 辞書で管理する
# d[A[i][j]] = [i,j] みたいな感じ
d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)

    p.append(q)


for l, r in LR:
    i = l % D - 1
    s = (l - 1) // D
    e = (r - 1) // D
    print(p[i][e] - p[i][s])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
h, w, d = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(h)]
q = int(readline())
LR = [tuple(map(lambda x:int(x)-1, readline().split())) for _ in range(q)]

D = dict()
for hi in range(h):
    for wi in range(w):
        D[A[hi][wi]-1] = [hi,wi]

DP = [0]*(h*w)
for i in range(d, h*w):
    px, py = D[i-d]
    x, y = D[i]
    DP[i] = DP[i-d] + abs(x-px) + abs(y-py)

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

Submission status: Accepted

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

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

d=[0]*(H*W)
for i in range(D, H*W):
  px,py = pos[i-D]
  x, y = pos[i]
  d[i]=d[i-D] + abs(x-px) + abs(y-py)

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

Submission status: Accepted

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

mp=[[0] for i in range(d)]

for i in range(d):
    tmp=i
    while tmp+d<h*w:
        x=abs(grid[tmp+d][0]-grid[tmp][0])+abs(grid[tmp+d][1]-grid[tmp][1])
        mp[i].append(x+mp[i][-1])
        tmp+=d
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    l,r=l-1,r-1
    tmp=mp[r%d][(r-(r%d))//d]-mp[l%d][(l-(l%d))//d]
    print(tmp)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


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

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    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)]

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [mp[r] - mp[l] for l, r in LR]
    ans = "\n".join(map(str, ans))
    return ans


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [mp[r] - mp[l] for l, r in LR]
    return ans


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = [0] * Q
    ans = dfs(H, W, D, A, Q, LR)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numpy as np

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(1,H+1,1):
    A = [0]+list(map(int,input().split()))
    for j in range(1,W+1,1):
        one_to_HW[A[j]] = [i,j]
    
path = [0]*(H*W+1)

for i in range(D,H*W+1,1):#一つ前からたどり着くのに魔力
    path[i]=abs(one_to_HW[i][0]-one_to_HW[i-D][0])+abs(one_to_HW[i][1]-one_to_HW[i-D][1])

for i in range(D,H*W+1,1):#累積
    path[i]=path[i]+path[i-D]

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

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

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

H,W,D = MI()
A = [LI() for i in range(H)]
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i,j)

B = [0]*(H*W+1)
for i in range(1,D+1):
    a = i+D
    while a <= H*W:
        B[a] = B[a-D] + abs(d[a][0]-d[a-D][0]) + abs(d[a][1]-d[a-D][1])
        a += D

Q = I()
for i in range(Q):
    L,R = MI()
    print(B[R]-B[L])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W, D = MAP()
A = [LIST() for _ in range(H)]
Q = INT()
LR = [LIST() for _ in range(Q)]

dic = [[] for _ in range(D)]

for y in range(H):
	for x in range(W):
		#print(dic)
		dic[A[y][x]%D].append([A[y][x], y, x])

for lis in dic:
	lis.sort(key = lambda x:x[0])

for lis in dic:
	lis[0][0] = 0
	for i in range(len(lis)):
		if i == len(lis)-1:
			break
		point = (lis[i][1], lis[i][2])
		dist_point = (lis[i+1][1], lis[i+1][2])
		lis[i+1][0] = lis[i][0] + abs(point[0] - dist_point[0]) + abs(point[1]-dist_point[1])

#print(dic)
for L, R in LR:
	print(dic[R%D][ceil(R/D)-1][0] - dic[R%D][ceil(L/D)-1][0])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [0]*(h*w+1)
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[j] = cost + roots[j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[r] - roots[l])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
power_acc[0].insert(0, 0)
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D] - power_acc[L%D][L//D])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	if L%D:
		print(power_acc[R%D][R//D] - power_acc[L%D][L//D])
	else:
		print(power_acc[R%D][R//D-1] - power_acc[L%D][L//D-1])