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())
A = [[-1,-1] for _ in range(H*W)]
for i in range(H):
    A_tmp = [int(x)-1 for x in input().split()]
    for j in range(W):
        A[A_tmp[j]] = [i,j]
        
Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]

M_sum = [] 
for i in range(H*W):
    if i<D:
        M_sum.append(0)
    else:
        M_sum.append(M_sum[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[i-D][1]))
        
for L,R in LR:
    print(M_sum[R-1]-M_sum[L-1])

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, size: int):
        self.__size = size
        self.__data = [0] * (size + 1)

    def update(self, idx: int, v: int):
        while idx <= self.__size:
            self.__data[idx] += v
            idx += idx & -idx

    def sum(self, l: int, r: int):
        """(l, r] の累積和
        """
        return self.__sum(r) - self.__sum(l)

    def __sum(self, idx: int):
        s = 0
        while idx > 0:
            s += self.__data[idx]
            idx -= idx & -idx
        return s


def practical_skill_test(
        H: int, W: int, D: int, A: list, Q: int, queries: list) -> list:
    # sorted_A = sorted([(A[h][w], h, w) for h in range(H) for w in range(W)])
    per_rem = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            per_rem[a % D].append((a, h, w))

    # あまりごとの累積和
    ss = []
    for d in range(D):
        per_rem[d].sort()

        n = len(per_rem[d])
        ss.append([0] * (n + 1))

        for idx in range(n-1):
            _, i, j = per_rem[d][idx]
            _, x, y = per_rem[d][idx + 1]
            # print('{}({},{}) -> {}({},{})'.format(a, i, j, b, x, y))

            ss[d][idx + 1] = ss[d][idx] + abs(x - i) + abs(y - j)

    res = []
    for l, r in queries:
        d = l % D
        if d > 0:
            li, ri = l // D, r // D
        else:
            li, ri = l // D - 1, r // D - 1
        res.append(ss[d][ri] - ss[d][li])

    return res


if __name__ == "__main__":
    H = 0
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    queries = [tuple(int(s) for s in input().split()) for _ in range(Q)]

    ans = practical_skill_test(H, W, D, A, Q, queries)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
L = []
for i in range(H):
  L.append(list(map(int,input().split())))
Q = int(input())
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
P = [[0,0]]*(H*W)
for i in range(H):
  for j in range(W):
    P[L[i][j]-1] = [i,j]
dp = [0]*(H*W)
for i in range(D):
  dp[i] = 0
  cnt = i+D
  while cnt < H*W:
    dp[cnt] = dp[cnt-D]+abs(P[cnt][0]-P[cnt-D][0])+abs(P[cnt][1]-P[cnt-D][1])
    cnt = cnt+D
for j in range(Q):
  print(dp[query[j][1]-1]-dp[query[j][0]-1])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
amd = {}
for i in range(h):
  al = map(int, input().split())
  for j, a in enumerate(al):
    amd[a] = (j+1, i+1)

dsum = [0 for _ in range(d+1)]
for i in range(d+1, h*w+1):
  dsum.append(dsum[-d] + abs(amd[i][0]-amd[i-d][0]) + abs(amd[i][1]-amd[i-d][1]))

q = int(input())
for _ in range(q):
  ans = 0
  l, r = map(int, input().split())
  print(dsum[r] - dsum[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())
L, R = zip(*(map(int, input().split()) for _ in range(Q)))

# 各整数の座標を調べる
p = {A[i][j]: (i, j) for i in range(H) for j in range(W)}

# 各整数に対する累積和を求める
dp = [0 for _ in range(H * W + 1)]
for x in range(D + 1, H * W + 1):
    y = x - D
    dp[x] = dp[y] + abs(p[x][0] - p[y][0]) + abs(p[x][1] - p[y][1])

# 各クエリに対する解を累積和を用いて求める
ans = '\n'.join(str(dp[r] - dp[l]) for l, r in zip(L, R))

# 出力
print(ans)

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())
L, R = zip(*(map(int, input().split()) for _ in range(Q)))
p = {A[i][j]: (i, j) for i in range(H) for j in range(W)}
dp = [0 for _ in range(H * W + 1)]
for x in range(D + 1, H * W + 1):
    y = x - D
    dp[x] = dp[y] + abs(p[x][0] - p[y][0]) + abs(p[x][1] - p[y][1])
ans = '\n'.join(str(dp[r] - dp[l]) for l, r in zip(L, R))
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, D = map(int, input().split())
    inv = [(0, 0)] * (H*W+1)
    for i in range(H):
        s = list(map(int, input().split()))
        for j in range(W):
            inv[s[j]] = (i, j)
    cumsum = [0] * (H*W+1)
    for x in range(1, H*W+1):
        if x-D > 0:
            ci, cj = inv[x]
            pi, pj = inv[x-D]
            cumsum[x] = cumsum[x-D] + abs(ci-pi) + abs(cj-pj)
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(cumsum[R] - cumsum[L])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = [0] * (H*W + 1)

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

    A = [0] * (H*W + 1)
    for l in range(H * W - D, 0, -1):
        a = d[l]
        b = d[l+D]
        A[l] = A[l+D] + abs(a[0] - b[0]) + abs(a[1] - b[1])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


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


tab = [ [0,0] ]*(w*h)

for hi in range(h):

    t = list(map(int,input().split()))

    for wi in range(w):
        tab[ t[wi]-1 ] = [hi, wi]

#print(tab)


cost = [0]*(w*h)
for i in range(d, w*h):
    a = tab[i-d]
    b = tab[i]

    cost[i] = abs( a[0]-b[0] ) + abs( a[1]-b[1] ) + cost[i-d]

#print(cost)

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:
H, W, D = map(int, input().split())
XY = [0] * (H * W)
for X in range(H):
    for Y, A in enumerate(map(int, input().split())):
        XY[A - 1] = (X, Y)
Q = int(input())
LR = []
for _ in range(Q):
    LR.append(list(map(int, input().split())))

toD = [0] * (H * W)
for i, (a, b) in enumerate(zip(XY, XY[D:]), D):
    toD[i] = abs(a[0] - b[0]) + abs(a[1] - b[1])

from itertools import accumulate
acc = [0] * (H * W)
for i in range(D):
    acc[i::D] = accumulate(toD[i::D])

for l, r in LR:
    ans = acc[r - 1] - acc[l - 1]
    print(ans)

Submission status: Accepted

Solution code:
# D
h, w, d = map(int, input().split())
points = [[0]*2 for i in range(h*w)]
cost = [0]* (h*w)
for h_i in range(h):
    a_row = [int(i) for i in input().split()]
    for r_i, a in enumerate(a_row):
        points[a-1][0] = h_i
        points[a-1][1] = r_i
for i in range(d, (h*w)):
    cost[i] = cost[i-d] + abs(points[i][0]-points[i-d][0]) + abs(points[i][1]-points[i-d][1])
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:
h, w, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
quest = [tuple(map(int, input().split())) for _ in range(q)]
enumboard = []
for i in range(h):
    for j in range(w):
        enumboard.append((board[i][j], i, j))
enumboard.sort(key = lambda x: x[0])
cumboard = [0 for _ in range(h*w)]
for i in range(d, h*w):
    cumboard[i] = cumboard[i-d] + abs(enumboard[i][1] - enumboard[i-d][1]) + abs(enumboard[i][2] - enumboard[i-d][2])
for l, r in quest:
    print(cumboard[r-1] - cumboard[l-1])

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())
B = [list(map(int, input().split())) for i in range(q)]

g = h * w

D = [[0, 0] for i in range(g+1)]
for i in range(h) :
    for j in range(w) :
        D[A[i][j]] = [i, j]
    

#print(D)
C = [0 for i in range(g+1)]


for i in range(1, (g+1)//d+2):
    for j in range(1, d+1) :
        if i*d+j <= g :
            #print(i*d+j)
            C[i*d+j] += C[i*d+j-d] + abs(D[i*d+j][0]-D[i*d+j-d][0]) + abs(D[i*d+j][1]-D[i*d+j-d][1])
        
#print(C)

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

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
hw = [[-1,-1]]*(h*w)
for i in range(h):
        ls = list(map(int,input().split()))
        for j in range(len(ls)):
                hw[ls[j]-1] = [j,i]
check = [0]*(h*w)
for i in range(h*w):
        if i + d > h*w-1:break
        check[i] = abs(hw[i][0]-hw[i+d][0]) + abs(hw[i][1]-hw[i+d][1])
ios = [0]*(w*h)
for i in range(d):
        c = 0;beforj = 0
        for j in range(h*w-1-i,-1,-d):
                if c == 0:c = 1;beforj = j;continue
                ios[j] = ios[beforj] + check[j]
                beforj = j
q = int(input())
for i in range(q):
        l,r = map(int,input().split())
        print(ios[l-1]-ios[r-1])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W,D = map(int, input().split())
M = [ list(map(int, input().split())) for _ in range(H)]
Q = int(input())
pos = {}
from itertools import accumulate

for h in range(H):
    for w in range(W):
        pos[M[h][w]] = (h,w)
        

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

distance = lambda p,np: abs(p[0]-np[0])+abs(p[1]-np[1])

for i in range(1,D+1):
    p = pos[i]
    amari = i % D

    tmp = i + D

    while tmp <= H*W:
        nextp = pos[tmp]
        accd[amari].append( accd[amari][-1] + distance(p,nextp) )

        tmp += D
        p = nextp

# print(accd)
# exit(0)

for i in range(Q):
    L,R = map(int, input().split())
    ans = 0

    if not L == R:
        if R%D == 0:
            ans = accd[L%D][(R-R%D)//D-1] - accd[L%D][(L-L%D)//D-1]
        else:
            ans = accd[L%D][(R-R%D)//D] - accd[L%D][(L-L%D)//D]


    print(ans)

Submission status: Accepted

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

h, w, d = map(int, input().split())
grid = [None]*(h*w)
for i in range(h):
    for j, c in enumerate(list(map(int, input().split()))):
        grid[c-1] = (i,j)
cost = {}
for i in range(h*w):
    now = h*w -1 - i
    up = now + d
    if up not in cost:
        cost[now] = 0
    else:
        cost[now] = cost[up] + calc_cost(grid[now], grid[up])

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

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
grid = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
info = [list(map(int,input().split())) for i in range(Q)]

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

cost = []
for s in range(D):
    acc = [0]
    tmp = 0
    for A in range(s,H*W+1-D,D):
        if s == 0 and A == 0:
            acc.append(tmp)
            continue
        i,j = note[A]; ni,nj = note[A+D]
        tmp += abs(ni-i) + abs(nj-j)
        acc.append(tmp)
    cost.append(acc)

def cal(n):
    L,R = info[n]
    index = L % D
    L = L // D; R = R // D
    ans = cost[index][R] - cost[index][L]
    return ans

for loop in range(Q):
    print(cal(loop))

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())
query = [list(map(int, input().split())) for _ in range(Q)]
dic = {}
for h in range(H):
    for w in range(W):
        dic[A[h][w] - 1] = (h, w)
c_sum = [0 for _ in range(H * W)]
for i in range(D):
    for j in range(i + D, H * W, D):
        x, y = dic[j - D]
        nx, ny = dic[j]
        c_sum[j] = c_sum[j - D] + abs(x - nx) + abs(y - ny)
for q in query:
    l, r = q
    print(c_sum[r - 1] - c_sum[l - 1])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
L=[0 for i in range(H*W+1)]
A=[]
for i in range(H):
    a=list(map(int,input().split()))
    A.append(a)
    
for i in range(H):
    for j in range(W):
        L[A[i][j]]=[i+1,j+1]
L[0]=[0,0]
#print(L)
l=[0 for i in range(H*W+1)]
for i in range(D):
    for j in range(H*W+1):
        if (i+j*D)>(H*W):
            break
        elif j==0:
            l[i+j*D]=0
        else:
            l[i+j*D]=l[i+(j-1)*D]+abs(L[i+j*D][0]-L[i+(j-1)*D][0])+abs(L[i+j*D][1]-L[i+(j-1)*D][1])
#print(l)
Q=int(input())
for i in range(Q):
    a,b=map(int,input().split())
    print(l[b]-l[a])

Submission status: Accepted

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

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

LR = []

for i in range(Q):
  LR.append(list(map(int, input().split())))

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(D + i, H * W, D):
    a = List[j - D]
    b = List[j]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1]) + Data[j - D]

for i in range(Q):
  print(Data[LR[i][1] - 1] - Data[LR[i][0] - 1])

Submission status: Accepted

Solution code:
N, W ,D = map(int, input().split())
inf = float("inf")
dp = [0]*(N*W)
s = [inf]*N*W

d = [list(map(int, input().split())) for i in range(N)]
T = int(input())
m = [list(map(int, input().split())) for i in range(T)]
ans = 0
 
for i in range(N):
    for j in range(W):
        s[d[i][j]-1] = [i,j]
k=0
#print(s)

for n in range(D,N*W):
    #print(n)
    dp[n] = dp[n-D]+abs(s[n][0]-s[n-D][0])+abs(s[n][1]-s[n-D][1])
    k+=1
for x,y in m:
    if x == y:print(0)
    else:print(dp[y-1]-dp[x-1])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l=[[0,0]]+[[]for _ in range(h*w)]
for i in range(h):
    for j,a in enumerate(map(int,input().split())):
        l[a]=[i,j]
for a in l[:d]:
    a.append(0)
for i,j in zip(l[d:],l):
    a,b=i
    x,y,v=j
    i.append(abs(x-a)+abs(y-b)+v)
l=[c for a,b,c in l]
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(l[b]-l[a])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l=[[0,0]]+[[]for _ in range(h*w)]
for i in range(h):
    for j,a in enumerate(map(int,input().split())):
        l[a]=[i,j]
for i in range(h*w+1):
    if i<d:
        l[i].append(0)
    else:
        a,b=l[i]
        x,y,v=l[i-d]
        l[i].append(abs(x-a)+abs(y-b)+v)
l=[a[2]for a in l]
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(l[b]-l[a])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l=[[0,0]]+[[]for _ in range(h*w)]
for i in range(h):
    for j,a in enumerate(map(int,input().split())):
        l[a]=[i,j]
for i in range(h*w+1):
    if i<d:
        l[i].append(0)
    else:
        a,b=l[i]
        x,y,v=l[i-d]
        l[i].append(abs(x-a)+abs(y-b)+v)
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(l[b][2]-l[a][2])

Submission status: Accepted

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

def dist(start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

D={} 
for i in range(h) :
    tmp=list(map(int,input().split()))
    for j in range(w):
        D[tmp[j]]=[i,j]
q=int(input())
A=[]
for _ in range(q):
    A.append(list(map(int,input().split())))
B=[0 for i in range(h*w)]
for i in range(h*w):
    if i>=d:
        B[i]=B[i-d]+dist(D[i+1],D[i-d+1])
for [l,r] in A:
    ans=B[r-1]-B[l-1]
    print(ans)

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
L = [[0,0] for _ in range(H*W+1) ]
for i in range(H):
    s = input().split()
    cnt = 0
    for x in s:
        L[int(x)]=[i,cnt]
        cnt += 1
M = [[0,0] for _ in range(H*W+1)]
for i in range(D,len(L)):
    M[i][0] = abs(L[i-D][0] - L[i][0])
    M[i][1] = abs(L[i-D][1] - L[i][1]) 
for i in range(D,len(L)):
    M[i][0] = M[i][0] + M[i-D][0]
    M[i][1] = M[i][1] + M[i-D][1]    
Q = int(input())
for i in range(Q):
    ans = 0
    x,y = map(int,input().split())
    ans += M[y][0] - M[x][0] 
    ans += M[y][1] - M[x][1]
    print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


h, w, d = LI()
coord = [0] * (h * w)
for y in range(h):
    for x, n in enumerate(LI_()):
        coord[n] = (y, x)

C = [[0] for _ in range(d)]
for i in range(d, h * w):
    diff = abs(coord[i][0] - coord[i - d][0]) + abs(coord[i][1] - coord[i - d][1])
    C[i % d].append(C[i % d][-1] + diff)

q = II()
for _ in range(q):
    l, r = LI_()
    n = l % d
    print(C[n][r // d] - C[n][l // d])

Submission status: Accepted

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

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

dist = [0]*(h*w)
for i in range(d,h*w):
    dist[i] = dist[i-d] + manhattan(A[i],A[i-d])

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

for ans in ans_list:
    print(ans)

Submission status: Accepted

Solution code:
# use faster method than input()
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


H, W, D = map(int, input().split())
A = [(0, 0)]*(H*W)
for r in range(H):
    l = list(map(int, input().split()))
    for c in range(W):
        A[l[c]-1] = (r, c)

dist = [0]*(H*W)
for i in range(D, H*W):
    dist[i] = dist[i-D]+manhattan(A[i], A[i-D])


Q = int(input())
L = []

ans_list = [0]*Q
for i in range(Q):
    ans = 0
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ans = dist[b]-dist[a]
    ans_list[i] = ans

for ans in ans_list:
    print(ans)

Submission status: Accepted

Solution code:
def cul_dis(start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

H,W,d = map(int,input().split())
number_pos = {}

for h in range(H) :
    state = list(map(int,input().split()))
    for i,number in enumerate(state):
        number_pos[number] = [h,i]

Q = int(input())

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

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

for i in range(H*W)[::-1]:
    if i+d <= H*W-1:
        mp_consume[i] = mp_consume[i+d]+cul_dis(number_pos[i+1],number_pos[i+d+1])

for [start,goal] in exams:
    ans = mp_consume[start-1]-mp_consume[goal-1]
    print(ans)

Submission status: Accepted

Solution code:
#入力
H,W,D = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(H)]

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

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

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

Submission status: Accepted

Solution code:
H,W,D = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
L_R = [list(map(int,input().split())) for i in range(Q)]
data = []
mod = [[0]]
for i in range(H):
    for j in range(W):
        data.append([A[i][j],i+1,j+1])

        
data.sort()

for i in range(H*W):
    if i <= D-1:
        mod.append([0])
    else:
        mod[(i%D)+1].append(mod[(i%D)+1][-1]+abs(data[i][1]-data[i-D][1])+abs(data[i][2]-data[i-D][2]))

for l,r in L_R:
    if l%D == 0:
        print(mod[D][(r//D)-1]-mod[D][(l//D)-1])
    else:
        print(mod[l%D][(r//D)]-mod[l%D][(l//D)])

Submission status: Accepted

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

zahyo=[[0,0]]*(h*w+1)
for i in range(h):
  for j in range(w):
    zahyo[a[i][j]]=[i,j]

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

Submission status: Accepted

Solution code:
# coding: utf-8


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

II = lambda: int(input())
MI = lambda: map(int, input().split())


def calc_scores(ad, D):
    def calc_score(i):
        x, y = ad[i]
        xp, yp = ad[i-D]
        return abs(x-xp) + abs(y-yp)
    scores = [0] * (D + 1)
    for i in range(D + 1, len(ad) + 1):
        scores.append(scores[i-D] + calc_score(i))
    return scores


def main():
    H, W, D = MI()
    ad = {}
    for i in range(H):
        for j, a in enumerate(MI()):
            ad[a] = (i, j)
    s = calc_scores(ad, D)
    for q in range(II()):
        L, R = MI()
        print(s[R] - s[L])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

coordinates = {}
for i in range(h):
    row = list(map(int, input().split()))
    for j in range(w):
        coordinates[row[j]] = (i, j)

costs = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    x1, y1 = coordinates[i]
    x2, y2 = coordinates[i - d]
    costs[i] = abs(x1 - x2) + abs(y1 - y2) + costs[i - d]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
dic=dict()
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        dic[A[j]]=(i,j)

Q=int(input())

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

for i in range(D+1,H*W+1):
    p,q = dic[i-D]
    x,y = dic[i]
    d[i]=d[i-D]+abs(p-x)+abs(q-y)


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

Submission status: Accepted

Solution code:
import math
def func(h, w, d, a, query):
    imos = [0 for _ in range(h*w)]
    pos = [[0, 0] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            pos[a[i][j]] = [i, j]
    for i in range(d):
        for j in range(math.ceil((h*w-i)/d)):
            if j == 0:
                continue
            else:
                imos[i + d * j] = imos[i + d * (j-1)]\
                                  + abs(pos[i + d * j][0] - pos[i + d * (j-1)][0])\
                                  + abs(pos[i + d * j][1] - pos[i + d * (j-1)][1])
    for i in range(len(query)):
        print(imos[query[i][1]] - imos[query[i][0]])
    return
h, w, d = [int(i) for i in input().split()]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    a[i] = [int(i) - 1 for i in input().split()]
q = int(input())
query = [[0, 0] for _ in range(q)]
for i in range(q):
    query[i] = [int(i) - 1 for i in input().split()]
func(h, w, d, a, query)
"""
func(3, 3, 2, [[0, 3, 2], [1, 4, 6], [7, 8, 5]], [[3, 7]])
print("ans: 5\n")
func(4, 2, 3, [[2, 6], [0, 3], [4, 1], [5, 7]], [[1, 1], [1, 1]])
print("ans: 0, 0\n")
func(5, 5, 4, [[12, 24, 6, 14, 16], [15, 21, 19, 1, 8], [13, 10, 11, 0, 18], [9, 5, 22, 7, 17], [2, 20, 4, 23, 3]], [[12, 12], [1, 9], [12, 12]])
print("ans: 0, 5, 0")
"""
# print("func({}, {}, {}, {}, {})".format(h, w, d, a, query))

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())
pos = [None]*(H*W+1)
for i, elem in enumerate(A):
    for j, a in enumerate(elem):
        pos[a] = (i, j)
acc = [[] for _ in range(D+1)]
for i in range(1, D+1):
    tmp = i
    s = 0
    acc[i].append(s)
    while tmp <= H*W-D:
        s += abs(pos[tmp][0]-pos[tmp+D][0])+abs(pos[tmp][1]-pos[tmp+D][1])
        acc[i].append(s)
        tmp += D

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

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    H, W, D = na[0], na[1], na[2]
    pos = [None] * (H * W)
    for i in range(H):
        na = list(map(int, input().split()))
        for j, a in enumerate(na):
            pos[a - 1] = (i, j)
    dist = [-1] * (H * W)
    for a in range(D):
        dist[a] = 0
    for a in range(D, H * W):
        x, y = pos[a]
        i, j = pos[a - D]
        dist[a] = dist[a - D] + abs(x - i) + abs(y - j)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

G = [[0, 0]] * (H * W + 1)

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

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

for i in range(D + 1, H * W + 1):
    x1, y1 = G[i]
    x2, y2 = G[i - D]
    S[i] += S[i - D] + abs(x1 - x2) + abs(y1 - y2)

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

Submission status: Accepted

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

# 各数字の座標
P = {}
for h in range(H):
    for w in range(W):
        P[A[h][w]] = (h, w)

# コスト(0番目は飾り)
C = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
    C[i] = C[i - D] + abs(P[i - D][0] - P[i][0]) + abs(P[i - D][1] - P[i][1])

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

Submission status: Accepted

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

import sys
input = sys.stdin.readline

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

# 各マス番号の座標位置をメモしておく
pos = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        pos[HW[i][j]] = (i, j)
# 間隔をDずつ空けた累積和
sm = [0] * (H*W+1)
for i in range(D+1, H*W+1):
    sm[i] = sm[i-D] + abs(pos[i][0] - pos[i-D][0]) + abs(pos[i][1] - pos[i-D][1])
# 各QはO(1)で解けるはず
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(sm[r] - sm[l])

Submission status: Accepted

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

a_list = [0]*(h*w+1)
for i in range(1, h*w+1):
    if i + d <= h*w:
        pos = a_dict[i]
        d_pos = a_dict[i+d]
        a_list[i+d] += a_list[i] + abs(d_pos[0]-pos[0]) + abs(d_pos[1]-pos[1])
for i in range(q):
    l, r = query[i]
    print(a_list[r] - a_list[l])

Submission status: Accepted

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

a_list = [0 for _ in range(h*w+1)]
for i in range(1, h*w+1):
    if i + d <= h*w:
        pos = a_dict[i]
        d_pos = a_dict[i+d]
        a_list[i+d] += a_list[i] + abs(d_pos[0]-pos[0]) + abs(d_pos[1]-pos[1])
for i in range(q):
    l, r = query[i]
    print(a_list[r] - a_list[l])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
zahyo = [0] * (h * w + 1)
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(w):
        zahyo[a[j]] = (i + 1, j + 1)
D = [0] * 100000
for i in range(d + 1, h * w + 1):
    D[i] = D[i - d] + abs(zahyo[i][1] - zahyo[i - d][1]) + abs(zahyo[i][0] - zahyo[i - d][0])
q = int(input())
for i in range(q):
    L, R = map(int, input().split())
    print(D[R] - D[L])

Submission status: Accepted

Solution code:
h,w,d = map(int, input().split())
c = {}
for i in range(h):
  x = list(map(int, input().split()))
  for j in range(w):
    c[x[j]] = [i,j]
# print(c)

a = [0] * (h*w-d+1)
b = [0] * (h*w+1)
for k in range(1, h*w-d+1):
  a[k] = abs(c[k+d][0]-c[k][0])+abs(c[k+d][1]-c[k][1])
for k in range(1, h*w-d+1):
  if k <= d:
    b[k+d] = a[k]
  else:
    b[k+d] = b[k] + a[k]
# print(b)

for _ in [0]*int(input()):
  l,r = map(int,input().split())
  print(b[r]-b[l])