Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.

Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.

Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Accepted

Solution code:
import collections
def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        L, R = map(int, input().split())
        queries.append([L, R])

    d = collections.defaultdict(list)
    for i in range(H):
        for j in range(W):
            d[A[i][j] % D].append([A[i][j], i, j])
    for v in d:
        d[v] = sorted(d[v], key = lambda x: x[0])

    d1 = collections.defaultdict(list)
    for v in d:
        prefix = [0]
        if v == 0:
            prefix.append(0)
        for i in range(len(d[v])-1):
            mag = abs(d[v][i][1] - d[v][i+1][1]) + abs(d[v][i][2]-d[v][i+1][2])
            prefix.append(prefix[-1]+mag)
        d1[v] = prefix
    # print(d1)

    # print(A)
    for L, R in queries:
        if L == R:
            print(0)
        else:
            l = (R-L) // D
            i = L // D
            v = L % D
            magic = d1[v][i+l] - d1[v][i]
            print(magic)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n//3)
    return

#B
def B():
    _ = II()
    s = S()
    print(["Three", "Four"][len(set(s)) - 4])
    return

#C
def C():
    return

class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)
#D
def D():
    h, w, d = LI()
    u = Value_UnionFind(h * w)
    field = defaultdict(list)
    for i in range(h):
        a = LI_()
        for j in range(w):
            field[a[j]] = [j, i]
    for i in range(h * w):
        if i + d < h * w:
            x1, y1 = field[i]
            x2, y2 = field[i + d]
            u.unit(i, i + d, abs(x1 - x2) + abs(y1 - y2))

    for _ in range(II()):
        l, r = LI_()
        print(u.differ(l, r))
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d - 1, -1, -1):
    accum_list[i] += (abs(num_dict[i + d][0] - num_dict[i][0]) +
                      abs(num_dict[i + d][1] - num_dict[i][1]) + accum_list[i + d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])

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 numpy as np

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
b = [list(map(int,input().split())) for _ in range(q)]
p =[0]*(h*w+1)
    
for i in range(h):
    for j in range(w):
        tmp = a[i][j]
        p[tmp] = [i,j]
cost = [0]*(h*w+1)
i = d+1
while i <= h*w:
    cost[i] = cost[i-d] + abs(p[i][0]-p[i-d][0]) + abs(p[i][1]-p[i-d][1])
    i += 1
for k in range(q):
    r = b[k][0]
    l = b[k][1]
    print(cost[l]-cost[r])

Submission status: Accepted

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

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

Q = int(input())
ANS = [0] * (H * W + 1)

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

place = []


for i in range(H):
    for j in range(W):
        place.append([grid[i][j], i, j])
place.sort()


classify = [[0] for i in range(D)]

for i in range(D):
    for j in range(i, H*W-D, D):
        classify[(i+1)%D].append(abs(place[j+D][1]-place[j][1])+abs(place[j+D][2]-place[j][2]) + classify[(i+1)%D][-1])

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

Submission status: Accepted

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


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    K = {}
    for i in range(H):
        for j in range(W):
            K[A[i][j]] = (i, j)
    B = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(D+1, H*W+1):
        j = i % D
        ti, tj = K[i]
        si, sj = K[i-D]
        B[ti][tj] = B[si][sj] + abs(ti-si) + abs(tj-sj)
    for q in range(Q):
        ri, rj = K[R[q]]
        li, lj = K[L[q]]
        s = B[ri][rj] - B[li][lj]
        print(s)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]"
    R = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

def magic(LR):
  magic = 0
  x = LR[0]
  y = LR[1]
  magicx = abs(A[x][0] - A[y][0]) 
  magicy = abs(A[x][1] - A[y][1]) 
  return magicx + magicy

magiclist = [0]*(H*W+1)
for i in range(D+1,H*W+1):
  magiclist[i] = magiclist[i-D] + magic([i-D,i])

for i in range(Q):
  x = LR[i][0]
  y = LR[i][1]
  if (x == y):
    print(0)
  else:
    print(magiclist[y]- magiclist[x])

Submission status: Accepted

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

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

c = [0]*d
for i in range(len((b))-d):
    c.append(abs(b[i+d][0]-b[i][0])+abs(b[i+d][1]-b[i][1])+c[-d])

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

Submission status: Accepted

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

pos = [0]*(H*W)
for j in range(H):
  A = list(map(int,input().split()))
  for i in range(W):
    pos[A[i]-1] = (i,j)
#print(link)

memo = [0]*(H*W)
for x in range(H*W):
  if x<D:
    continue
  i,j = pos[x-D][0],pos[x-D][1]
  u,v = pos[x  ][0],pos[x  ][1]
  memo[x] = memo[x-D]+abs(i-u)+abs(j-v)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[(0,0) for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    mod_array_cumsum = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(D):
        cumsum = 0
        prev_position = mod_array[row_number][0]
        for column_number in range(1, H*W//D+1):
            position = mod_array[row_number][column_number]
            cumsum += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            mod_array_cumsum[row_number][column_number] = cumsum
            prev_position = position

    # print(mod_array_cumsum)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = mod_array_cumsum[L%D][R//D] - mod_array_cumsum[L%D][L//D]
        print(ans)
        

main()

Submission status: Accepted

Solution code:
H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W//D+1) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# あまりごとに累積和を取っておく
acc = [[0] * (H*W//D+1) for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y
# print(acc)

Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    ans = acc[m][g] - acc[m][s]
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
  h, w, d = map(int, input().split())
  axy = [None for _ in range(h*w+1)]
  for y in range(h):
    for x, a in enumerate(map(int, input().split())):
      axy[a] = (x, y)

  dlist = [0 for _ in range(h*w+1)]
  for a in range(d+1, h*w+1):
    dlist[a] = dlist[a-d] + abs(axy[a][0] - axy[a-d][0]) + abs(axy[a][1] - axy[a-d][1])

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


if __name__ == '__main__':
  main()

Submission status: Accepted

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

place = [None]*(H*W+1)
for h in range(H):
    for w in range(W):
        place[A[h][w]] = (h, w)
place[0] = (0, 0)
dis = [[0 for _ in range((H*W)//D+1)] for _ in range(D)]
for i, (x, y) in enumerate(place):
    if i <= D:
        continue
    bx, by = place[i-D]
    dis[i%D][i//D] = dis[i%D][i//D-1] + abs(x-bx) + abs(y-by)


for l, r in LR:
    ans = dis[r%D][r//D] - dis[l%D][l//D]
    print(ans)

Submission status: Accepted

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

array_len = math.ceil(H*W/D)

a_array = [[[0, 0] for _ in range(array_len)] for _ in range(D)]
for i in range(H):
    A = map(int, input().split())
    for j, a in enumerate(A):
        a = a - 1
        a_array[a % D][a//D][0] = i + 1
        a_array[a % D][a//D][1] = j + 1

# print(a_array)
sum_array = [[0] * array_len for _ in range(D)]
for i in range(D):
    s = 0
    for j in range(1, array_len):
        s += (abs(a_array[i][j][0]-a_array[i][j-1][0]) +
              abs(a_array[i][j][1]-a_array[i][j-1][1]))
        sum_array[i][j] = s

# print(sum_array)

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    d = (R-1) % D
    l_power = sum_array[d][(L-1-d)//D]
    r_power = sum_array[d][(R-1-d)//D]
    print(r_power-l_power)

Submission status: Accepted

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



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


address = {}
dist = {}
for i in range(d+1):
    dist[i] = 0


for y in range(h):
    for x in range(w):
        address[graph[y][x]] = [y, x]


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


for i, j in query:
    print(dist[j] - dist[i])

Submission status: Accepted

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

d = [None for _ in range(H * W + 1)]
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

cumsum = [0 for _ in range(H * W + 1)]
for m in range(1, D + 1):
    i = m
    while i <= H * W:
        if i - D <= 0:
            i += D
            continue
        x1, y1 = d[i - D]
        x2, y2 = d[i]
        dist = abs(x2 - x1) + abs(y2 - y1)
        cumsum[i] = cumsum[i - D] + dist
        i += D

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

Submission status: Accepted

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

#盤面を取得
lst = [0] * (H * W + 1)
for i in range(1, H + 1):
    tmp = list(map(int, input().split()))
    for j in range(1, W + 1):
        lst[tmp[j - 1]] = [i, j]
#前処理

#xからyに移動するのにかかるコストを返す関数
def cost(x, y): 
    return abs(lst[x][0] - lst[y][0]) + abs(lst[x][1] - lst[y][1])

check_lst = [False] * (H * W + 1)
cost_lst = [0] * (H * W + 1)
for i in range(1, D + 1):
    if check_lst[i]:
        continue
    check_lst[i]  = True
    tmp = i
    while tmp + D <= H * W:
        cost_lst[tmp + D] = cost_lst[tmp] + cost(tmp, tmp + D)
        check_lst[tmp + D] = True
        tmp += D

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

Submission status: Accepted

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

#盤面を取得
lst = [0] * (H * W + 1)
for i in range(1, H + 1):
    tmp = list(map(int, input().split()))
    for j in range(1, W + 1):
        lst[tmp[j - 1]] = [i, j]
#前処理

#xからyに移動するのにかかるコストを返す関数
def cost(x, y): 
    return abs(lst[x][0] - lst[y][0]) + abs(lst[x][1] - lst[y][1])

check_lst = [False] * (H * W + 1)
cost_lst = [0] * (H * W + 1)
for i in range(1, H * W + 1):
    if check_lst[i]:
        continue
    check_lst[i]  = True
    tmp = i
    while tmp + D <= H * W:
        cost_lst[tmp + D] = cost_lst[tmp] + cost(tmp, tmp + D)
        check_lst[tmp + D] = True
        tmp += D

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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i,j]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
S=[0]*(h*w+1)
for k in range(d+1,h*w+1):
    x,y=adress[k]
    i,j=adress[k-d]
    S[k]=S[k-d]+abs(x-i)+abs(y-j)
for x,y in order:
    print(S[y]-S[x])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
 
S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)
 
for l, r in LR:
    print(S[r] - S[l])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = list(list(map(int,input().split()))for i in range(H))
B = [[0,0]for i in range(H*W)]
for i in range(H):
    for j in range(W):
        B[A[i][j]-1] = [i,j]
MP = [0]*(H*W)
for i in range(D):
    x,y = B[i]
    for j in range(i+D,H*W,D):
        MP[j] = MP[j-D] + abs(x-B[j][0]) + abs(y-B[j][1])
        x,y = B[j]
for i in range(int(input())):
    l,r = map(int,input().split())
    print(MP[r-1]-MP[l-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    # 各数字の座標をhw[]に格納
    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]

    # for i in range(len(hw)):
    #     print(i, hw[i])
    
    # Dのmodごとにmod Dからの距離を計算(累積和)
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            # print("{} - {} : {}".format(tmp-D, tmp, tmp_cost))
            # print(hw[tmp-D], hw[tmp], abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1]))
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    # print(modd)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

a = [[0 for _ in range(w)] for _ in range(h)]
masu = {}
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j in range(w):
        masu[a[i][j]] = (i,j)

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


q = int(input())
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        ans[i] = 0
    else:
        ans[i] = point[r] - point[l]
 
for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))

S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)

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

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*((h*w+1)//d+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    X,Y = s[i]
    Z,W = s[i-d]
    x = abs(X - Z) + abs(Y - W)
    D[i%d][i//d] = x + D[i%d][i//d-1]
for _ in range(q):
    l,r = map(int,input().split())
    x = D[l%d]
    print(x[r//d] - x[l//d])

Submission status: Accepted

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

N = H*W
C = [0]*N
pos = [(0,0)]*N
for i in range(H):
    for j in range(W):
        a = A[i][j]-1
        pos[a] = (i,j)
for i in range(D,N):
    C[i] = sum(abs(pos[i][xy]-pos[i-D][xy]) for xy in range(2))
S = [0]*(N+1)
for i in range(D,N+1):
    S[i] = C[i-1] + S[i-D]

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

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
index = [(0,0) for x in range(h*w+1)]
for i in range(1,h+1):
    col = list(map(int, input().split()))
    for j in range(1,w+1):
        index[col[j-1]] = (i, j)

memo = [0 for x in range(h*w+1)]
l = 0
for l in range(1, h*w+1-d):
    memo[l+d] = memo[l] + abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])

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

Submission status: Accepted

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

ACCUM = [0] * (H*W+1)
POS = [None] * (H*W+1)

for i in range(H):
    for j in range(W):
        num=A[i][j]
        POS[num]=(i,j)

for start in range(1,D+1):
    i=start
    cost=0
    while i <= H*W:
        pos0 = POS[i]
        i += D
        if i > H*W: break
        pos1 = POS[i]
        cost += abs(pos0[0]-pos1[0]) + abs(pos0[1]-pos1[1])
        ACCUM[i] = cost

for q in range(Q):
    l,r = LR[q]
    print(ACCUM[r]-ACCUM[l])

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]] = (i, j)

    q = int(input())

    dp = [0]*(row*col+1)
    for j in range(d+1, row*col+1):
        x_map_y = abs(x_map[j][0] - x_map[j-d][0])
        x_map_x = abs(x_map[j][1] - x_map[j-d][1])
        dp[j] = dp[j-d]+x_map_y+x_map_x
#        print("j {0} x_map_y : {1} x_map_x : {2} dp[j] : {3}".format(
#            j, x_map_y, x_map_x, dp[j]))

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


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
px = [0] * (H*W+1)
py = [0] * (H*W+1)
d = [0] * (H*W+1)

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = dp[j - D] + abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    print(dp[qy] - dp[qx])

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

numbers = {}
for y in range(H):
	for x in range(W):
		numbers[A[y][x]] = (y, x)

numbers_sum = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
	f, t = numbers[n], numbers[n - D]
	cost = abs(f[0] - t[0]) + abs(f[1] - t[1])
	numbers_sum[n] = numbers_sum[n - D] + cost

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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[]
l=[[] for i in range(h*w+1)]
for i in range(h):
    p=[int(j) for j in input().split()]
    a.append(p)
    for j in range(w):
        l[int(p[j])].append(i)
        l[int(p[j])].append(j)
cost=[0 for i in range(h*w+1)]
for i in range(1,h*w+1-d):
    cost[i+d]=cost[i]+abs(l[i+d][0]-l[i][0])+abs(l[i][1]-l[i+d][1])
q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    print(cost[lr[1]]-cost[lr[0]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

from collections import defaultdict
H, W, D = map(int, input().split())
dic = defaultdict()
for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        dic[a[j]] = [i, j]
dist = [0 for i in range(H*W+1)]
for i in range(1, D+1):
    for j in range(i, H*W-D+1, D):
        dist[j+D] = abs(dic[j][0] - dic[j+D][0]) + abs(dic[j][1] - dic[j+D][1])
for i in range(1, D+1):
    for j in range(i+D, H*W+1, D):
        dist[j] += dist[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:
import sys
input = sys.stdin.readline

h,w,d = map(int,input().split())
ahw = [0]*(h*w)
dp = [0]*(h*w)
for i in range(h):
  temp = [int(i)-1 for i in input().split()]
  for j in range(w):
    ahw[temp[j]] = (i,j)
for i in range(d):
  dp[i] = 0
for i in range(d,h*w):
  dp[i] = dp[i-d] + abs(ahw[i][0]-ahw[i-d][0]) + abs(ahw[i][1]-ahw[i-d][1])

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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
integer=[0]*(1+h*w)
for i in range(h):
    a_list=list(map(int,input().split()))
    for j in range(w):
        integer[a_list[j]]=((i+1,j+1))
dp=[0]*(1+h*w)
for i in range(h*w-d+1,h*w+1):
    dp[i]=0
    pre=i
    now=i-d
    while now>0:
        dp[now]=dp[pre]+abs(integer[now][0]-integer[pre][0])+abs(integer[now][1]-integer[pre][1])
        pre=now
        now=now-d
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(dp[l]-dp[r])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*H]
Q=int(input())
LR=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*Q]
dic=[None]*(H*W)
dic2=[None]*(H*W)

for i in range(H):
    for j in range(W):
        dic[A[i][j]]=(i,j)

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

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

Submission status: Accepted

Solution code:
H,W,D = map(int, input().split())
A = {}
for i in range(H):
    for j, s in enumerate(input().split()):
        A[int(s)] = [i,j]
Q = int(input())
exam = []
for i in range(Q):
    exam.append(list(map(int, input().split())))

grid = [0]
manta = lambda x,y:abs(x[0]-y[0])+abs(x[1]-y[1])
for i in range(1, H*W+1):
    if (i-1) // D == 0:
        grid.append(0)
    else:
        grid.append(manta(A[i], A[i-D]) + grid[i-D])
for l,r in exam:
    print(grid[r]-grid[l])

Submission status: Accepted

Solution code:
H,W,D = map(int, input().split())
grid_dict = {}
for i in range(H):
    for j,s in enumerate(input().split()):
        grid_dict[int(s)] = [i,j]

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

man = lambda x,y: abs(x[0]-y[0])+abs(x[1]-y[1])

power = [[0] for i in range(D)]
power[0].append(0)
for i in range(1,H*W+1):
    if i + D not in grid_dict:
        break
    power[i%D].append(power[i%D][-1] + man(grid_dict[i], grid_dict[i+D]))
# [print(i) for i in power]

for l,r in exam:
    if r == l:
        print(0)
        continue
    print(power[r%D][r//D]-power[r%D][l//D])