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:
from collections import defaultdict
def main():
    # init
    h,w,d = map(int,input().split())
    dic = defaultdict(list)
    for i in range(h):
        nums = [int(x) for x in input().split()]
        for j,num in enumerate(nums):
            dic[int(num)] = [i,j]
    # memo
    ls = [0 for i in range(w*h+1)]
    for i in range(d+1,w*h+1):
        before,after = dic[i-d],dic[i]
        diff = abs(after[0]-before[0]) + abs(after[1]-before[1])
        ls[i] = ls[i-d]+ diff
    # ans
    q = int(input())

    for i in range(q):
        l,r = map(int,input().split())
        print(ls[r]-ls[l])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Num = [0]*H*W

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


Q = int(input())

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

S = []
for i in range(D):
    s = [0]
    score = 0
    num = i+D
    while num<H*W:
        score += abs(Num[num][0]-Num[num-D][0])+abs(Num[num][1]-Num[num-D][1])
        num += D
        s.append(score)
    S.append(s)

for b in B:
    d = (b[0]-1)%D
    n1 = (b[1]-1)//D
    n0 = (b[0]-1)//D
    print(S[d][n1]-S[d][n0])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

H,W,D = II()
A = []
for _ in range(H):
    A.append(III())
Q = I()
L,R = Line(Q,2)

d = defaultdict(tuple)
for i in range(H):
    for j in range(W):
        d[A[i][j]-1] = (i,j)

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

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

Submission status: Accepted

Solution code:
import numpy as np
H, W, D = map(int, input().split())
grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = [int(_) for _ in input().split()]
memo = [None] * (H * W + 1)
for h in range(H):
    for w in range(W):
        memo[grid[h][w]] = (h, w)

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

for d in range(D + 1, H * W + 1):
    h_1, w_1 = memo[d]
    h_0, w_0 = memo[d - D]
    distance[d] = distance[d - D] + abs(h_1 - h_0) + abs(w_1 - w_0)

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

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
px = [0]*(H*W+1)
py = [0]*(H*W+1)
dp = [0]*(H*W+1)
for i in range(H):
  inf = input().split()
  for j in range(W):
    a = int(inf[j])
    py[a] = i
    px[a] = j
for i in range(D+1, H*W+1):
  dp[i] = dp[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())
  print(dp[R]-dp[L])

Submission status: Accepted

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

S=[0]*(h*w+1)
add={}

for i in range(h):
    for j in range(w):
        add[box[i][j]]=[i,j]

for k in range(d+1,h*w+1):
    x,y=add[k]
    i,j=add[k-d]
    S[k]=S[k-d]+abs(x-i)+abs(y-j)

for s,g in order:
    print(S[g]-S[s])

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

#受け取りなど
H, W, D = getlist()
a = []
mp = [0] * (H * W + 1)
for i in range(H):
	A = getlist()
	for j in range(W):
		a.append([A[j], i, j])

#前計算
a = sorted(a)
for i in range(D, H * W):
	mp[i] += mp[i - D] + abs(a[i][1] - a[i - D][1]) + abs(a[i][2] - a[i - D][2])

#計算
Q = int(input())
for i in range(Q):
	L, R = getlist()
	print(mp[R - 1] - mp[L - 1])

Submission status: Accepted

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

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 h_i in range(h):
    for w_i in range(w):
        xy.append((a[h_i][w_i], h_i + 1, w_i + 1))

xy.sort()
acm = [[0] for i in range(d)]
for i in range(d, h * w):
    magic = abs(xy[i][1] - xy[i-d][1]) + abs(xy[i][2] - xy[i-d][2])
    acm[i%d].append(acm[i%d][-1] + magic)

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

Submission status: Accepted

Solution code:
# ABC089D - Practical Skill Test
def main():
    # find cumulative sum using a period of D O(N) -> O(1) for each query
    H, W, D, *X = map(int, open(0).read().split())
    memo = [None] * (H * W + 1)  # memo[x] := coordinate of x
    for i, a in enumerate(zip(*[iter(X[: H * W])] * W), 1):
        for j, x in enumerate(a, 1):
            memo[x] = (i, j)
    dist = [0] * (H * W + 1)  # dist[x] := distance to x from 1
    for r in range(D + 1, H * W + 1):
        (rx, ry), (lx, ly) = memo[r], memo[r - D]
        dist[r] = dist[r - D] + abs(rx - lx) + abs(ry - ly)
    ans = []
    for l, r in zip(*[iter(X[H * W + 1 :])] * 2):
        ans.append(dist[r] - dist[l])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC089D - Practical Skill Test
def main():
    H, W, D, *X = map(int, open(0).read().split())
    memo = [None] * (H * W + 1)  # memo[x] := coordinate of x
    for i, a in enumerate(zip(*[iter(X[: H * W])] * W), 1):
        for j, x in enumerate(a, 1):
            memo[x] = (i, j)
    dist = [0] * (H * W + 1)  # dist[x] := distance to x from 1
    for r in range(D + 1, H * W + 1):
        rx, ry = memo[r]
        l = r - D
        lx, ly = memo[r - D]
        dist[r] = dist[l] + abs(rx - lx) + abs(ry - ly)
    ans = []
    for l, r in zip(*[iter(X[H * W + 1 :])] * 2):
        ans.append(dist[r] - dist[l])
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC089D - Practical Skill Test
def main():
    H, W, D, *X = map(int, open(0).read().split())
    memo = [None] * (H * W + 1)  # memo[i] := coordinate of i
    for i, a in enumerate(zip(*[iter(X[: H * W])] * W), 1):
        for j, x in enumerate(a, 1):
            memo[x] = (i, j)
    dist = [0] * (H * W + 1)  # dist[i] := distance to i from 1
    for r in range(D + 1, H * W + 1):
        rx, ry = memo[r]
        l = r - D
        lx, ly = memo[r - D]
        dist[r] = dist[l] + abs(rx - lx) + abs(ry - ly)
    ans = []
    for l, r in zip(*[iter(X[H * W + 1 :])] * 2):
        ans.append(dist[r] - dist[l])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC089D - Practical Skill Test
def main():
    H, W, D, *X = map(int, open(0).read().split())
    memo = {}  # memo[i] := coordinate of i
    for i, a in enumerate(zip(*[iter(X[: H * W])] * W), 1):
        for j, x in enumerate(a, 1):
            memo[x] = (i, j)
    dist = [0] * (H * W + 1)  # dist[i] := distance to i from 1
    for r in range(D + 1, H * W + 1):
        rx, ry = memo[r]
        l = r - D
        lx, ly = memo[r - D]
        dist[r] = dist[l] + abs(rx - lx) + abs(ry - ly)
    ans = []
    for l, r in zip(*[iter(X[H * W + 1 :])] * 2):
        ans.append(dist[r] - dist[l])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
l=[None]*(H*W+1)
for i in range(H):
    s=tuple(map(int,input().split()))
    for j in range(W):
        l[s[j]]=(i,j)
S=[0]*(H*W+1)
for i in range(D+1,H*W+1):
    S[i]=S[i-D]+abs(l[i][0]-l[i-D][0])+abs(l[i][1]-l[i-D][1])
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    print(S[R]-S[L])

Submission status: Accepted

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

Q = int(input())
dp = [H*W+2]*(H*W+1)

for i in range(1,H*W+1):
    if i > D:
        dp[i] = dp[i-D] + abs(mass[i][0] - mass[i-D][0]) + abs(mass[i][1] - mass[i-D][1])
    else:
        dp[i] = mass[i][0] + mass[i][1]

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

Submission status: Accepted

Solution code:
def solve():
	h,w,d,*l=map(int,open(0).read().split())
	s=h*w+1;x=[0]*s;y=[0]*s;k=[0]*s
	for i,a in enumerate(l[:s-1]):x[a]=i//w;y[a]=i%w
	for i in range(d+1,s):k[i]=k[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
	for l,r in zip(l[s::2],l[s+1::2]):print(k[r]-k[l])
if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
h,w,d,*l=map(int,open(0).read().split())
s=h*w+1;x=[0]*s;y=[0]*s;k=[0]*s
for i,a in enumerate(l[:s-1]):x[a]=i//w;y[a]=i%w
for i in range(d+1,s):k[i]=k[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for l,r in zip(l[s::2],l[s+1::2]):print(k[r]-k[l])

Submission status: Accepted

Solution code:
h,w,d,*l=map(int,open(0).read().split())
s=h*w
x=[0]*(s+1)
y=[0]*(s+1)
for i,a in enumerate(l[:s]):
	x[a]=i//w
	y[a]=i%w
ref=[0]*(s+1)
for i in range(d+1,s+1):
	ref[i]=ref[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for l,r in zip(l[s+1::2],l[s+2::2]):
	print(ref[r]-ref[l])

Submission status: Accepted

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

C = [-1] * H*W
for i in range(H*W-D):
    fx, fy = B[i+D]
    tx, ty = B[i]
    C[i] = abs(fx-tx)+abs(fy-ty)

E = [0] * H*W
for i in range(D):
    S = 0
    for j in range(i, H*W-D, D):
        S += C[j]
        E[j+D] = S
# print(E)

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

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]

pos = [None for _ in range(h * w + 1)]
for y in range(h):
    for x in range(w):
        pos[ls[y][x]] = (x, y)

ds = []
for i in range(d):
    ps = pos[1 + i::d]
    temp = [0]
    for x, y in zip(ps, ps[1:]):
        z = abs(x[0] - y[0]) + abs(x[1] - y[1])
        temp.append(temp[-1] + z)
    ds.append(temp)

for l, r in qs:
    l -= 1
    r -= 1
    ps = ds[l % d]
    print(ps[r // d] - ps[l // d])

Submission status: Accepted

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

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

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

a2dist = [0]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i+D] = a2dist[i]+dist(a2pos[i],a2pos[i+D])
  
q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  print(a2dist[r]-a2dist[l])

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

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

q = [[] for _ in range(D)]
for y, a in enumerate(A):
    for x, s in enumerate(a):
        q[s%D].append((s, x, y))

q = [sorted(q_i) for q_i in q]
# print(q)
t = [[q_j[0] for q_j in q_i] for q_i in q]
p = []
for q_i in q:
    p.append([])
    bx, by = 0, 0
    for q_j in q_i:
        _, x, y = q_j
        p[-1].append(abs(x-bx)+abs(y-by))
        bx, by = x, y
    p[-1] = [0] + list(accumulate(p[-1][1:]))

# print(p)
# print(t)

for l, r in LR:
    start = bisect(t[l%D], l)-1
    end = bisect(t[l%D], r)-1
    print(p[l%D][end]-p[l%D][start])
    # print(start, end, t[l%D], p[l%D])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A=[]
for i in range(H):
  temp=list(map(int,input().split()))
  for j in range(W):
    A.append([temp[j],i+1,j+1])
Q=int(input())
B=[]
for i in range(Q):
  B.append(list(map(int,input().split())))
A.sort()
#print(A)

C=[0]*(H*W)
for i in range(H*W-1,-1,-1):
  if i+D<=H*W-1:
    C[i]=C[i+D]+abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
#print(C)

for i in range(Q):
  print(C[B[i][0]-1]-C[B[i][1]-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    H,W,D = map(int,input().split())
    A = [list(map(int,input().split())) for i in range(H)]
    Q = int(input())
    
    a = {}
    for i in range(H):
        for j in range(W):
            a[A[i][j]] = [i,j]
    
    c = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i+D <= H*W:
            j,k = a[i]
            x,y = a[(i+D)]
            c[i+D] = abs(x-j) + abs(y-k)

    import copy
    d =  copy.deepcopy(c)
    
    for i in range(1,D+1):
        tmp = i
        while tmp+D <= H*W:
            d[tmp+D] += d[tmp]
            tmp += D
    #print(c)
    #print(d)
    for i in range(Q):
        L,R = map(int,input().split())
        ans = d[R] - d[L]
        print(ans)
    
    
    
main()

Submission status: Accepted

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

def ipt():
    for x in range(H):
        A = list(map(int, input().split()))
        for y in range(W):
            mp[A[y]] = (x, y)


ipt()
Q = int(input())

def get_dist(prev, x):
    dx = mp[x][0] - mp[prev][0]
    dy = mp[x][1] - mp[prev][1]
    return abs(dx) + abs(dy)


dist = [0 for i in range(H*W+1)]
for i in range(0, D):
    tmp = 0
    for x in range(1+i, H*W-D+1, D):
        tmp += get_dist(x, x+D)
        dist[x+D] = tmp


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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
nums=[[0 for s in range(w)] for i in range(h)]
gya=[[0,0] for i in range(h*w)]
for i in range(h):
    nums[i]=list(map(int,input().split()))
    for j in range(w):
        gya[nums[i][j]-1]=[i,j]
cost=[0]*(h*w+d)
for i in range(d):
    s=i
    while s<h*w-d:
        cost[s+d]=cost[s]+abs(gya[s+d][0]-gya[s][0])+abs(gya[s+d][1]-gya[s][1])
        s+=d
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(cost[r-1]-cost[l-1])

Submission status: Accepted

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

    c = [0] * (H * W)
    for i in range(H):
        for j in range(W):
            c[field[i][j] - 1] = (i, j)
    
    d = [0] * (H * W)
    for l in range(H * W - D):
        i, j = c[l]
        x, y = c[l + D]
        d[l+D] = d[l] + abs(x - i) + abs(y - j)
    
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(d[R-1]-d[L-1])


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

H, W, D = map(int, input().split())
A = [[int(i) - 1 for i in input().split()] for _ in range(H)]
Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]

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

cost = [0] * (H * W)
def dfs(i, px, py) :
    if i + D >= H * W :
        return 0
        
    cx, cy = place[i + D]
    cost[i] = dfs(i + D, cx, cy) + abs(cx - px) + abs(cy - py)
    return cost[i]
    
for i in range(D) :
    dfs(i, place[i][0], place[i][1])
    
for l, r in LR :
    print(cost[l-1] - cost[r-1])

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());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

h, w, d = getList()
INF = 1000000000

revindex = [(0, 0) for i in range(h*w)]
acc = [0 for i in range(h*w)]

white = 0
for i in range(h):
    a = getList()
    for j, num in enumerate(a):
        revindex[num-1] = (i, j)

for i in range(d):
    tmp = 0
    idx = i

    while(True):
        pa, pb = revindex[idx]
        idx += d
        if idx >= w * h:
            break
        pc, pd = revindex[idx]
        tmp += (abs(pa - pc) + abs(pb - pd))
        acc[idx] = tmp


q = getN()
for i in range(q):
    f, l = getList()
    print(acc[l-1] - acc[f-1])

# print(acc)

Submission status: Accepted

Solution code:

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

field = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        field[A[j]] = (i,j)

Q = int(input())


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

"""
for i in range(1,D+1):
    tmp = 0
    cum[i] = 0
    n = D
    while i+n <= H*W:
        cum[i+n] = cum[i+n-D] + abs(field[i+n][0] - field[i+n-D][0]) + abs(field[i+n][1] - field[i+n-D][1])
        #print("---", i+n, cum[i+n], field[i+n][0] , field[i+n-D][0], field[i+n][1] , field[i+n-D][1])
        n += D
"""
#print(cum)
LR = [None] * Q
for i in range(Q):
    L, R = map(int, input().split())
    LR[i] = (L,R)

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

Submission status: Accepted

Solution code:

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

field = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        field[A[j]] = (i,j)

Q = int(input())


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

"""
for i in range(1,D+1):
    tmp = 0
    cum[i] = 0
    n = D
    while i+n <= H*W:
        cum[i+n] = cum[i+n-D] + abs(field[i+n][0] - field[i+n-D][0]) + abs(field[i+n][1] - field[i+n-D][1])
        #print("---", i+n, cum[i+n], field[i+n][0] , field[i+n-D][0], field[i+n][1] , field[i+n-D][1])
        n += D
"""
#print(cum)
for i in range(Q):
    L, R = map(int, input().split())
    print(cum[R] - cum[L])

#print(field)

Submission status: Accepted

Solution code:

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

field = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        field[A[j]] = (i,j)

Q = int(input())


cum = [0] * (H*W+1)
for i in range(1,D+1):
    tmp = 0
    cum[i] = 0
    n = D
    while i+n <= H*W:
        cum[i+n] = cum[i+n-D] + abs(field[i+n][0] - field[i+n-D][0]) + abs(field[i+n][1] - field[i+n-D][1])
        n += D


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

Submission status: Accepted

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

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

# MAX_LOG = math.ceil(math.log2(h*w))
MAX_LOG = 18
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


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

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


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

ruisekiwa = [0] * (H*W+1)
for d in range(1,D+1):
    x,y = numlist[d]
    tmp = 0
    for i in range(d,H*W+1,D):
        x2,y2 = numlist[i]
        tmp += abs(x-x2)+abs(y-y2)
        x,y = x2,y2
        ruisekiwa[i] = tmp

for i in range(Q):
    start,goal = LR[i]
    ans = ruisekiwa[goal] - ruisekiwa[start]
    
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  h,w,d  = (int(i) for i in input().split())
  a = [list(map(int, input().split())) for _ in range(h)]

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      query[a[i][j] - 1] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  ans = deque([])
  for i in range(q):
    l,r = (int(m) for m in input().split())
    ans.append(distance[r-1]-distance[l-1])
  print("\n".join(map(str,ans)))
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  h,w,d  = (int(i) for i in input().split())
  a = [list(map(int, input().split())) for _ in range(h)]
  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      query[a[i][j] - 1] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  ans = deque([])
  for i in range(q):
    l,r = (int(m) for m in input().split())
    ans.append(str(distance[r-1]-distance[l-1]))
  print("\n".join(ans))
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  h,w,d  = (int(i) for i in input().split())
  a = deque([])
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      query[a[i][j] - 1] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  ans = []
  for i in range(q):
    l,r = (int(m) for m in input().split())
    ans.append(distance[r-1]-distance[l-1])
  print("\n".join(map(str,ans)))
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  h,w,d  = (int(i) for i in input().split())
  a = deque([])
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      query[a[i][j] - 1] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)

  for i in range(q):
    l,r = (int(m) for m in input().split())
    print(distance[r-1]-distance[l-1])
    
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  
  for i in range(d,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)
  #print(distance)
  
  for i in range(q):
    l,r = (int(m) for m in input().split())
    print(distance[r-1]-distance[l-1])
  
solve()

Submission status: Accepted

Solution code:
def main():
    H, W, D = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(H)]
    max_ = (((H * W) // D) + 1)
    cost = [[0] * max_ for i in range(D)]
    xy = [None] * (H*W)
    for i in range(H):
        for j in range(W):
            xy[a[i][j] - 1] = [i, j]
    
    cost = [0] * (H*W)
    for start in range(1, D+1):
        now = start + D - 1
        while now < H*W:
            x, y = xy[now]
            px, py = xy[now-D]
            cost[now] = cost[now - D] + abs(px - x) + abs(py - y)
            now += D
    
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(cost[r-1] - cost[l-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())

nlis = [0]
for i in range(H * W):

    i += 1

    if i - D < 1:
        nlis.append(0)

    else:
        now = dic[i]
        las = dic[i-D]
        nlis.append(nlis[i-D] + abs(now[0]-las[0]) + abs(now[1]-las[1]))


for i in range(Q):

    L,R = map(int,input().split())

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

Submission status: Accepted

Solution code:
F=lambda:map(int,input().split());H,W,D=F();d={};e=[0]*H*W
for i in range(H):
 for j,v in enumerate(F()):d[v-1]=(i,j)
for i in range(D,H*W):e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for i in range(int(input())):l,r=F();print(e[r-1]-e[l-1])

Submission status: Accepted

Solution code:
F=lambda:map(int,input().split())
H,W,D=F();d={};e=[0]*H*W
for i in range(H):
 for j,v in enumerate(F()):d[v-1]=(i,j)
for i in range(H*W):
 if i>=D:e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for i in range(int(input())):l,r=F();print(e[r-1]-e[l-1])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split());S=H*W;A=[map(int,input().split())for _ in range(H)];d=[0]*S;e=[0]*S
for i,l in enumerate(A):
 for j,v in enumerate(l):d[v-1]=(i,j)
for i in range(S):
 if i>=D:e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for i in range(int(input())):l,r=map(int,input().split());print(e[r-1]-e[l-1])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A=[map(int,input().split())for _ in range(H)]
Q=int(input())
L=[map(int, input().split())for _ in range(Q)]
d=[None for _ in range(H*W)]
for i,l in enumerate(A):
 for j,v in enumerate(l):d[v-1]=(i, j)
e=[0for _ in range(H*W)]
for i in range(H*W):
 if i>=D:e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for l,r in L:print(e[r-1]-e[l-1])

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

dp = [None for _ in range(H*W)]
for i, l in enumerate(A) :
    for j, v in enumerate(l) :
        dp[v-1] = (i, j)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        pass
    else :
        distance[i] = f(i-D, i) + distance[i-D]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)

# costの辞書化
from collections import defaultdict
cost_dict = defaultdict(lambda: {})
N = H*W+1
for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    cost_dict[s][g] = cost
    

dist = defaultdict(lambda: {})
for i in range(1, D+1):
    dist[i][i] = 0
    s = i
    g = i+D
    while g < N:
        dist[i][g] = dist[i][s] + cost_dict[s][g]
        s = g
        g = s + D

    
#print(dist)
for l, r in LR:
    idx = r%D
    if idx == 0:
        idx = D
    print(dist[idx][r]-dist[idx][l])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
M = [(-1, -1)]*(H*W+1)
A = []
for i in range(H):
  As = list(map(int, input().split()))
  for j in range(W):
    a = As[j]
    M[a] = (i, j)
  A.append(As)
#print(M)
Dist = [0]*(H*W+1)
for k in range(0, H*W-D+1):
  i, j = M[k]
  x, y = M[k+D]
  Dist[k+D] = Dist[k]+abs(x-i)+abs(y-j)
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  r = Dist[R]-Dist[L]
  print(r)

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)]
x=[0]*(h*w+1)
y=[0]*(h*w+1)
for i in range(1,h+1):
    for j in range(1,w+1):
        x[a[i-1][j-1]]=i
        y[a[i-1][j-1]]=j
dp=[0]*(h*w+1)
for i in range(d+1,h*w+1):
    dp[i]=dp[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])

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