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:
h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

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

for i in range(h):
    for j in range(w):
        s = a[i][j]
        arr[s] = (i, j)

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


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

Submission status: Accepted

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

h,w,d=nii()

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

b_dict={}
for i in range(1,h*w+1):
  if i-d<=0:
    b_dict[i]=0
  else:
    oy,ox=a_dict[i-d]
    ny,nx=a_dict[i]
    b_dict[i]=b_dict[i-d]+abs(ny-oy)+abs(nx-ox)

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

P = [[]]
for i in range(1,D+1):
    q = [0]
    k = i + D
    while k <= H*W:
        p = abs(dict[k][0] - dict[k-D][0]) + abs(dict[k][1] - dict[k-D][1])
        q.append(q[-1]+p)
        k = k + D
    P.append(q)

Q = int(input())

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

Submission status: Accepted

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

place=[(0,0) for _ in range(h*w+1)]

for r in range(h):
    for c in range(w):
        place[a[r][c]]=(r,c)

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


for r in range(1,w*h+1):
    if r-d<1:
        continue

    r1,c1=place[r-d]
    r2,c2=place[r]

    dp[r]=dp[r-d]+abs(r1-r2)+abs(c1-c2)

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

    print(dp[r]-dp[l])

Submission status: Accepted

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

h,w,d=nii()

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

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<=h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

Submission status: Accepted

Solution code:
h,w,D = map(int,input().split())
a=[]

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

d={}
for i in range(h):
    c=a[i]
    for j in range(w):
        d[c[j]]=(i+1,j+1)


R_min=h*w
R_max=1
query=[]
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    query.append([l,r])
    R_min = min(l,R_min)
    R_max = max(r,R_max)


cum=[0]*(h*w+1)
for k in range(R_min,R_max-D+1):
    prev = cum[k-1]
    cost = abs(d[k+D][0]-d[k][0]) + abs(d[k+D][1]-d[k][1])
    cum[k+D-1]=cost+prev



for j in range(q):
    l,r=query[j][0],query[j][1]
    score = cum[r-1]-cum[l-1]
    print(score)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, D = mapint()
As = [list(mapint()) for _ in range(H)]

points = [0]*(H*W)
for i in range(H):
    for j in range(W):
        points[As[i][j]-1] = (i, j)
from collections import defaultdict
from itertools import accumulate
dic = defaultdict(list)

for i in range(1, D+1):
    h, w = points[i-1]
    cnt = 0
    while i+cnt*D<=H*W:
        h2, w2 = points[i+cnt*D-1]
        dic[i].append(abs(h2-h)+abs(w2-w))
        h, w = h2, w2
        cnt += 1
    dic[i] = list(accumulate(dic[i]))

Q = int(input())
for _ in range(Q):
    L, R = mapint()
    base = L%D
    if base==0:
        base = D
    l = (L-base)//D
    r = (R-base)//D
    print(dic[base][r]-dic[base][l])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
C = {i:0 for i in range(1,H*W+1)}
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i,j)
dist = {i:[] for i in range(1,D+1)}
for i in range(1,D+1):
    dist[i].append(0)
    y0,x0 = C[i]
    for j in range(1,(H*W-i)//D+1):
        y1,x1 = C[i+j*D]
        dist[i].append(dist[i][-1]+abs(y1-y0)+abs(x1-x0))
        y0 = y1
        x0 = x1
Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    i = L%D
    if i==0:
        i = D
    j1 = (L-i)//D
    j2 = (R-i)//D
    print(dist[i][j2]-dist[i][j1])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]

inf = 1 << 30

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

for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (i, j)

for i in range(1, h * w):
    if dist[i] == inf:
        dist[i] = 0
        j = i + d
        while j <= h * w:
            dist[j] = dist[j - d] + abs(pos[j][0] - pos[j - d][0]) + \
                abs(pos[j][1] - pos[j - d][1])
            j += d


q = int(input())
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())

al = [list(map(int, input().split())) for _ in range(h)]
v_to_xy = [(-1,-1)]*(h*w+1)
v_to_xy[0] = v_to_xy[d]
for i in range(h):
    for j in range(w):
        v_to_xy[al[i][j]] = (i,j)

dd = []
for i in range(d):
    csum = 0
    cumsum = []
    prev = v_to_xy[i]
    for j in range(i,h*w+1,d):
        if j == 0:
            cumsum.append(0)
            continue
        x,y = v_to_xy[j]
        diff = abs(prev[0]-x) + abs(prev[1]-y)
        csum += diff
        cumsum.append(csum)
        prev = (x,y)
    dd.append(cumsum)
    
# print(dd)

ansl = []
for _ in range(int(input())):
    l,r = map(int, input().split())
    drem = r%d
    ri = (r-drem)//d
    li = (l-drem)//d
    # print(drem,li,ri)
    ans = dd[drem][ri] - dd[drem][li]
    ansl.append(ans)

for ans in ansl: print(ans)

Submission status: Accepted

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

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
Q = int(input())
lis = [0] * (h * w)
for i in range(h):
    for j in range(w):
        lis[a[i][j] - 1] = (i, j)
cum = [0] * d
for i in range(d, h * w):
    cum.append(cum[i - d] + abs(lis[i][0] - lis[i - d][0]) + abs(lis[i][1] - lis[i - d][1]))
for i in range(Q):
    l, r = map(int, input().split())
    print(cum[r - 1] - cum[l - 1])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A = [[0]*(W+1)]
A += [[0] + list(map(int,input().split())) for _ in range(H)]
# n2idx = [None]*(H*W + 1)
routes = [[] for _ in range(D)]
for h in range(1, H+1):
    for w in range(1, W+1):
        # n2idx[A[h][w]] = (h, w)
        routes[A[h][w]%D].append((A[h][w], h, w))
        #(num, x-idx, y-idx)

Q = int(input())
costs = [[0] for _ in range(D)]
for d in range(D):
    routes[d].sort()
    # now = routes[d][0]
    for i in range(1, len(routes[d])):
        v1, h1, w1 = routes[d][i-1]
        v2, h2, w2 = routes[d][i]
        costs[d].append(costs[d][i-1] + abs(h1-h2)+abs(w1-w2))

for _ in range(Q):
    L, R = map(int, input().split())
    amari = L%D
    start = L//D
    end = R//D
    if amari == 0:
        start -= 1
        end -= 1
    print(costs[amari][end] - costs[amari][start])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
x = [0] * (H * W + 1)
for i in range(H):
  a = list(map(int, input().split()))
  for j in range(W):
    x[a[j]] = [i, j]
    
#print(x)
d = [0] * (H * W + 1)
for i in range(1, H * W + 1):
  if i > D:
    d[i] = d[i - D] + abs(x[i][0] - x[i - D][0]) + abs(x[i][1] - x[i - D][1])

#print(d)    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(d[r] - d[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)]
    B = [[] for _ in range(H * W + 1)]
    for h in range(H):
        for w in range(W):
            B[A[h][w]] = (h,w)
    C = []
    for d in range(1,D+1):
        tmp = []
        x, y = B[d]
        pre = 0
        while d <= H * W:
            nx, ny = B[d]
            now = abs(nx - x) + abs(ny - y) + pre
            tmp.append(now)
            pre = now
            x, y = nx, ny
            d += D
        C.append(tmp)
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        index = L % D
        index -= 1
        cnt = L // D
        if L % D == 0:
            cnt -= 1
        ans = C[index][cnt + (R - L) // D] - C[index][cnt]
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
X = [(0,0) for _ in range(H*W)]
Y = [0 for _ in range(H*W)]

for i in range(H):
    A = [int(x)-1 for x in readline().split()]
    for j in range(W):
        X[A[j]] = (i,j)

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

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

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
P = [None]*(H*W+1)

for h in range(H):
  A = list(map(int,input().split()))
  for w in range(W):
    P[A[w]] = [h,w]

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

for n in range(D+1,H*W+1):
  B[n] = B[n-D]+abs(P[n][0]-P[n-D][0])+abs(P[n][1]-P[n-D][1])

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
L=["*"]*(H*W)

for y in range(H):
    B=list(map(int,input().split()))
    for x in range(W):
        L[B[x]-1]=(x,y)

G=[[0]*((H*W+D-1)//D) for _ in range(D)]

for i in range(H*W-D):
    (X1,Y1)=L[i]
    (X2,Y2)=L[i+D]

    p,q=i//D,i%D
    G[q][p+1]=G[q][p]+abs(X1-X2)+abs(Y1-Y2)

Q=int(input())
X=[0]*Q

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

    p,r=L//D,L%D
    q=R//D
    X[k]=G[r][q]-G[r][p]

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

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
Aindex = [0] * (H*W)
for h in range(H):
    w = 0
    for A in input().split():
        Aindex[int(A)-1] = (h,w)
        w += 1 

import numpy as np
v, h = int(np.ceil(H*W/D)), D
Mp = np.zeros((v, h), dtype='int64') #MpをMod D別に計算する予定
mp = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1]) #魔力計算する関数
for x in range(D,H*W):
    i, j = divmod(x, D)
    Mp[i,j] = mp(Aindex[x], Aindex[x-D])
#縦軸方向に累積和を取っておき、後のクエリにO(1)で対応
Mp = Mp.cumsum(axis=0)

#クエリ処理
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
for l,r in Query:
    ans = Mp[divmod(r-1, D)] - Mp[divmod(l-1, D)]
    print(ans)

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
Aindex = [0] * (H*W)
for h in range(H):
    w = 0
    for A in input().split():
        Aindex[int(A)-1] = (h,w)
        w += 1 

import numpy as np
v, h = int(np.ceil(H*W/D)), D
Mp = np.zeros((v, h)) #MpをMod D別に計算する予定
mp = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1]) #魔力計算する関数
for x in range(D,H*W):
    i, j = divmod(x, D)
    Mp[i,j] = mp(Aindex[x], Aindex[x-D])
#縦軸方向に累積和を取っておき、後のクエリにO(1)で対応
Mp = Mp.cumsum(axis=0)

#クエリ処理
Q = int(input())
Query = [(int(x) for x in input().split()) for _ in range(Q)]
for l, r in Query:
    ans = Mp[divmod(r-1, D)] - Mp[divmod(l-1,D)]
    print(int(ans))

Submission status: Accepted

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

x_axis = [0]*(H*W)
y_axis = [0]*(H*W)

for i in range(H):
  A = list(map(lambda x: int(x)-1, input().split()))
  for j in range(W):
    x_axis[A[j]] = j
    y_axis[A[j]] = i

def dis(a, b):
  return abs(x_axis[a]-x_axis[b]) + abs(y_axis[a]-y_axis[b])

magic = [[0] for _ in range(D)]

for i in range(D):
  temp = i
  while temp < H*W-D:
    magic[i].append(magic[i][-1] + dis(temp, temp+D))
    temp += D

Q = int(input())
for _ in range(Q):
  L, R = map(lambda x: int(x)-1, input().split())
  L, d = divmod(L, D)
  R //= D
  print(magic[d][R] - magic[d][L])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
inv_A = [(0, 0)] * (H*W+1)
for y, a in enumerate(A):
    for x, a_ in enumerate(a):
        inv_A[a_] = (y, x)
C = [0] * D
c = 0
for i in range(D, H*W+1):
    y1, x1 = inv_A[i]
    y2, x2 = inv_A[i-D]
    C.append(abs(y1-y2)+abs(x1-x2)+C[i-D])
Ans = []
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    Ans.append(C[r]-C[l])
print("\n".join(map(str, Ans)))

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
# 1, 2, ..., H*Wの座標を記録
G = [(-10**9, -10**9) for _ in range(H * W + 1)]

for i in range(H):
    line = list(map(int, input().split()))
    for j in range(W):
        grid = int(line[j])
        G[grid] = (i, j)

# 1,2,...,H*Wまで行くために必要なコスト
cost = [0 for _ in range(H * W + 1)]
for i in range(D + 1, H * W + 1):
    cost_x = abs(G[i][0] - G[i - D][0])
    cost_y = abs(G[i][1] - G[i - D][1])
    cost[i] = cost[i - D] + cost_x + cost_y

ans = []

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

# print(G)
# print(cost)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def get_dist(cur, nxt):
    return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])


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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate


def get_dist(cur, nxt):
    return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])


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

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

acc = []
for i in range(D):
    res = [0]
    now = i
    while now + D < H * W:
        nxt = now + D
        res.append(get_dist(pos[now], pos[nxt]))
        now = nxt
    acc.append(list(accumulate(res)))

Q = int(input())
for _ in range(Q):
    ans = 0
    L, R = map(int, input().split())
    L -= 1
    R -= 1
    path = acc[L % D]
    print(path[R // D] - path[L // D])

Submission status: Accepted

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

lis=[[] for i in range(h*w)]
for i in range(h):
  ai=list(map(int,input().split()))
  for j in range(w):
    lis[ai[j]-1].append(i)
    lis[ai[j]-1].append(j)

U=[]

for i in range(d):
  Ui=[0]
  j=1
  while i+j*d<h*w:
    Ui.append(Ui[j-1]+abs(lis[i+j*d][0]-lis[i+(j-1)*d][0])
              +abs(lis[i+j*d][1]-lis[i+(j-1)*d][1]))
    j+=1
  U.append(Ui)

q=int(input())


for i in range(q):
  li,ri=map(lambda x:int(x)-1,input().split())
  modi=li%d
  print(U[modi][(ri-modi)//d]-U[modi][(li-modi)//d])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
basyo=[[]for i in range(h*w)]
hako=[]
a=[0 for i in range(h*w)]
for i in range(h):
    hako.append(list(map(int,input().split())))
for i in range(h):
    for j in range(w):
        basyo[hako[i][j]-1].append([i,j])

for i in range(d):
    a[i]=0
    tmp=0
    while i<h*w-d :
        ni=i+d
        t=abs(basyo[i][0][0]-basyo[ni][0][0])+abs(basyo[i][0][1]-basyo[ni][0][1])
        tmp+=t
        a[ni]=tmp
        i=ni
q=int(input())
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(a[y]-a[x])

Submission status: Accepted

Solution code:
from collections import defaultdict
H,W,D = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for h in range(H):
    grid[h] = list(map(int, input().split()))
number_yx = [[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x in range(W):
        number_yx[grid[y][x]] = [y,x]
fromto_cost = defaultdict(lambda: defaultdict(int))
for mod_group in range(D):
    # 剰余ごとにスタートを決定
    start = mod_group+1
    previous = start
    fromto_cost[start][start] = 0
    previous_y, previous_x = number_yx[previous]
    cost = 0
    while previous+D <= (H*W):
        Next = previous+D 
        Next_y, Next_x = number_yx[Next]
        cost += abs(Next_y-previous_y) + abs(Next_x-previous_x)
        fromto_cost[start][Next] = cost

        previous = Next
        previous_y,previous_x = Next_y,Next_x

Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
    start, goal = map(int,input().split())
    mod = start % D
    base = mod
    if base == 0:
        base = D 
    base_to_goal = fromto_cost[base][goal]
    base_to_start = fromto_cost[base][start]
    ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
    print(ans)

Submission status: Accepted

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

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

cost=[0]*(h*w)

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


ans=0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, D = LI()
    A = [LI_() for _ in range(H)]
    Q = I()

    c = [[] for _ in range((H * W))]
    for i, j in itertools.product(range(H), range(W)):
        c[A[i][j]] = [i, j]

    c_cum = [0] * (H * W)
    for i in range(H * W - D):
        c_cum[i+D] = (abs(c[i+D][0] - c[i][0]) + abs(c[i+D][1] - c[i][1])) + c_cum[i]

    for _ in range(Q):
        L, R = LI_()
        ans = c_cum[R] - c_cum[L]
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, d = mapint()
As = [list(mapint()) for _ in range(H)]
Q = int(input())

from collections import defaultdict
dic = {}
for h in range(H):
    for w in range(W):
        a = As[h][w]
        dic[a] = (h, w)

cost_dic = defaultdict(int)
for i in range(d+1, H*W+1):
    oh, ow = dic[i-d]
    h, w = dic[i]
    cost_dic[i] = cost_dic[i-d]+abs(h-oh)+abs(w-ow)

for _ in range(Q):
    l, r = mapint()
    print(cost_dic[r]-cost_dic[l])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, d = mapint()
As = [list(mapint()) for _ in range(H)]
Q = int(input())

from collections import defaultdict
from itertools import accumulate
from bisect import bisect_left
dic = defaultdict(list)
for h in range(H):
    for w in range(W):
        a = As[h][w]
        dic[a%d].append((a, h, w))

cost_dic = {}
for m in dic.keys():
    dic[m].sort()
    sa, sh, sw = dic[m][0]
    cost_dic[m] = [0]
    for a, h, w in dic[m][1:]:
        cost = abs(h-sh)+abs(w-sw)
        cost_dic[m].append(cost)
        sa, sh, sw = a, h, w
    cost_dic[m] = list(accumulate(cost_dic[m]))

for _ in range(Q):
    l, r = mapint()
    sidx = bisect_left(dic[l%d], (l, 0, 0))
    eidx = bisect_left(dic[l%d], (r, 0, 0))
    print(cost_dic[l%d][eidx]-cost_dic[l%d][sidx])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
lst = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        lst[a[j]] = (i,j)
cost = [0]*(h*w+1)
for t in range(1,d+1):
    now = t
    while now <= h*w-d:
        nxt = now+d
        x0,y0 = lst[now]
        x1,y1 = lst[nxt]
        cost[nxt] = cost[now]+abs(x0-x1)+abs(y0-y1)
        now += d
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(cost[r]-cost[l])

Submission status: Accepted

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

max_value = H*W

position = [0]*(max_value+1)

root_cost = [0]*(max_value+1)

for y in range(H):
    A = list(map(int,input().split()))
    for x in range(W):
        position[A[x]] = (x+1,y+1)

for i in range(1,max_value+1):
    if 0 < i-D:
        x1,y1 = position[i-D]
        x2,y2 = position[i]
        root_cost[i] = root_cost[i-D]+(abs(x2-x1)+abs(y2-y1))

Q=int(input())

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])

Submission status: Accepted

Solution code:
import sys
readline=sys.stdin.readline
read=sys.stdin.read
 
h,w,d=map(int,readline().split())
a=[list(map(int,readline().split())) for _ in range(h)]
q,*lr=map(int,read().split())

ca=dict()
for i,l in enumerate(a):
  for j,e in enumerate(l):
    ca[e]=(i+1,j+1)
mp=[[0]*((h*w)//d+1) for _ in range(d)]
for i,mpl in enumerate(mp):
  for j,_ in enumerate(mpl[:-1]):
    if 0<i+d*j<=h*w-d:
      mpl[j+1]=mpl[j]+abs(ca[i+d*j][0]-ca[i+d*(j+1)][0])\
                +abs(ca[i+d*j][1]-ca[i+d*(j+1)][1])
for l,r in zip(*[iter(lr)]*2):
  print(mp[l%d][r//d]-mp[l%d][l//d])

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai - 1] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i]
        num = i + d
        while num < h * w:
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x, y = xi, yi
            num += d

    q = ni()
    for _ in range(q):
        l, r = ns()
        l, r = l - 1, r - 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai - 1] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i]
        num = i
        while num + d < h * w:
            num += d
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x, y = xi, yi

    q = ni()
    for _ in range(q):
        l, r = ns()
        l, r = l - 1, r - 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i + 1]
        num = i + 1
        while num + d <= h * w:
            num += d
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x = xi
            y = yi

    q = ni()
    for _ in range(q):
        l, r = ns()
        l -= 1
        r -= 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

memo = [-1]*(H*W+1)
for i in range(1,D+1):
    useMP = 0
    direct = range(i,H*W+1,D)
    memo[i]=0
    for p in range(len(direct)-1):
        x0,y0 = dict_map[direct[p]]
        x1,y1 = dict_map[direct[p+1]]
        dist = abs(x0-x1)+abs(y0-y1)
        useMP += dist
        memo[direct[p+1]]=useMP

for q in range(Q):
    L,R=LR[q]
    print(memo[R]-memo[L])

Submission status: Accepted

Solution code:
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d+1, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)

Submission status: Accepted

Solution code:
import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)

# Dで分類した累積和
# S[initial % D][j], n = r + D*j
S = [0 for _ in range(H*W+D)]
for i in range(D+1, H*W+1):
    x, y = num[i]
    a, b = num[i-D]
    S[i] = S[i-D] + abs(x - a) + abs(y - b)
# print(S)
Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[R] - S[L])