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())
p=[0]*(h*w+d*2)
s=[0]*(h*w+d*2)
for x in range(h):
	y=1
	for a in map(int,input().split()):
		p[a]=[x,y]
		y+=1
for i in range(1,h*w+1-d):
	s[i+d]=s[i]+abs(p[i+d][0]-p[i][0])+abs(p[i+d][1]-p[i][1])
for i in range(int(input())):
	l,r=map(int,input().split())
	print(s[r]-s[l])

Submission status: Accepted

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

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

costs = {i: 0 for i in range(1, D+1)}
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current] = costs[current-D] + abs(position[current][0] - position[current-D][0]) + abs(position[current][1] - position[current-D][1])
        current += D

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

Submission status: Accepted

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

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

costs = [0]*(H*W)
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current - 1] = costs[current - 1 - D] + abs(pos[current - 1][0] - pos[current - 1 - D][0]) + abs(pos[current - 1][1] - pos[current - 1 - D][1])
        current += D

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

Submission status: Accepted

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = time[l] + (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return time[en-1] - time[st-1]


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))

Submission status: Accepted

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

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(D + 1, H * W + 1):
    y = x - D
    p1, p2 = pos[x], pos[y]
    dt[x] = dt[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(queries, H, W, D):
    dp = [0] * (H*W+1)
    for i in range(D+1, H*W+1):
        dp[i] = dp[i-D] + sub_solve(i-D, i)

    for l, r in queries:
        ans = dp[r] - dp[l]
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())

    for y in range(1, H+1):
        tmp = [int(x) for x in input().split()]
        for x, i in enumerate(tmp, start=1):
            numbers[i] = (x, y)

    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    solve(queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def d_practical_skill_test(H, W, D, A, Q, I):
    # クエリが1-indexedなため、配列もそれに従う(0番は使わない)
    px = [0 for _ in range(H * W + 1)]
    py = [0 for _ in range(H * W + 1)]  # (px[Aij],py[Aij])にAijの値が入っている
    d = [0 for _ in range(H * W + 1)]  # 1~D→ゴールまでのコスト
    for i in range(H):
        for j in range(W):
            px[A[i][j]] = i
            py[A[i][j]] = 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])
    ans = []
    for l, r in I:
        ans.append(str(d[r] - d[l]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))

Submission status: Accepted

Solution code:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[] for i in range(D)]

    for i in range(0, H * W):
        A = i + 1
        if len(dp[A % (D)]) == 0:
            dp[A % (D)].append((A, 0))
        else:
            (prev_point, prev_cost)= dp[A % D][len(dp[A % D]) - 1]
            prev_pos = num_dic[prev_point]
            now_pos = num_dic[A]
            dp[A % (D)].append((A, prev_cost +abs(prev_pos[0] - now_pos[0]) + abs(prev_pos[1] - now_pos[1])))

    for test in test_list:
        L = test[0]
        R = test[1]
        if L==R:
            print 0
        else:
            print (dp[L % (D)] [R/(D) - 1 + (1 if R % D != 0 else 0)][1] -
                    (dp[L % (D)] [L/(D) - 1 + (1 if L % D != 0 else 0)][1] ))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}

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


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))

Submission status: Accepted

Solution code:
import numpy as np
H,W,D = map(int,input().split())
SUM = H*W
px = np.zeros(SUM+1)
py = np.zeros(SUM+1)
for i in range(1,H+1):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        px[A[j]] = i
        py[A[j]] = j + 1

d = np.zeros(SUM+1)
for t in range(D+1,SUM+1):
    d[t] = d[t-D] + abs(px[t] - px[t-D])+ abs (py[t] - py[t-D]);
        
Q = int(input())
L = []
R = []
for i in range(Q): 
    l,r = map(int, input().split())
    print(int(d[r]-d[l]))

Submission status: Accepted

Solution code:
def d_practical_skill_test(H, W, D, A, Q, I):
    # クエリが1-indexedなため、配列もそれに従う
    px = [0 for _ in range(H * W + 1)]
    py = [0 for _ in range(H * W + 1)]  # (px[i],py[j])にAijの値が入っている
    d = [0 for _ in range(H * W + 1)]
    for i in range(H):
        for j in range(W):
            px[A[i][j]] = i
            py[A[i][j]] = 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])
    ans = []
    for l, r in I:
        ans.append(str(d[r] - d[l]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))

Submission status: Accepted

Solution code:
# coding=utf-8
line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)

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())
LR = [list(map(int, input().split())) for i in range(Q)]
d = [0] * ((H*W)+1)
num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for i in range(D+1, H*W+1):
    d[i] = d[i-D] + abs(num_dict[i][0]-num_dict[i-D][0]) + abs(num_dict[i][1]-num_dict[i-D][1])
for l, r in LR:
    print(d[r]-d[l])

Submission status: Accepted

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

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

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

s = [[0] * (h * w // d + 1) for i in range(d)]

for i in range(d):
    for j in range(1, h * w // d + 1):
        b = i + d * (j - 1)
        c = i + d * j

        if c >= len(dic):
            break
        
        y, x = dic[b]
        ny, nx = dic[c]
        s[i][j] = s[i][j - 1] + abs(ny - y) + abs(nx - x)

q = int(input())

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

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

d = defaultdict(int)
for i in range(D + 1, H * W + 1):
    d[i] = d[i - D] + abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])


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

pos=[(0,0) for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        pos[int(a)-1]=(i,j)

q=int(input())


distances=[0 for _ in range(h*w)]

for i in range(d,h*w):
    a=h*w-i
    i,j=pos[a-1]
    x,y=pos[a+d-1]
    distances[a-1]=distances[a+d-1]+abs(i-x)+abs(j-y)

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

Submission status: Accepted

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

cost = {}
for i in range(1, W * H + 1):
    cost[i] = cost[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1]) if i > D else 0

Q = int(input())
for _ 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())
p = {}
for i in range(H):
    inp = list(map(int, input().split()))
    for j, value in enumerate(inp):
        p[value] = (i, j)

cost = {}
for i in range(1, W * H + 1):
    cost[i] = cost[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1]) if i > D else 0

Q = int(input())
for _ 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())
A = [[] for i in range(H)]

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

cum_sum = [0] * (H * W + 1)
for i in range(1, H * W - D + 1):
	crow = rev[i] // W
	ccol = rev[i] % W
	nrow = rev[i + D] // W
	ncol = rev[i + D] % W
	cum_sum[i + D] = cum_sum[i] + abs(crow - nrow) + abs(ccol - ncol)

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

Submission status: Accepted

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

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

from collections import defaultdict

dt = defaultdict(int)
for x in range(D + 1, H * W + 1):
    y = x - D
    p1 = pos[x]
    p2 = pos[y]
    dt[x] = dt[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

Submission status: Accepted

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

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

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

s = [0] * (h * w)
        
for i in range(d, h * w):
    j = i - d
        
    y, x = dic[j]
    ny, nx = dic[i]
    s[i] = s[i - d] + abs(ny - y) + abs(nx - x)

q = int(input())

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

Submission status: Accepted

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

location_x=[0 for i in range(h*w)]
location_y=[0 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        location_x[a[i][j]-1]=j
        location_y[a[i][j]-1]=i

mpp=[0 for i in range(h*w)]

for i in range(d):
    j=1
    while i+j*d<=h*w-1:
        mpp[ i+j*d]=mpp[ i+j*d-d]+abs(location_x[i+j*d-d]-location_x[i+j*d])+abs(location_y[i+j*d-d]-location_y[i+j*d])
        j+=1

for i in range(q):
    print( mpp[lr[i][1]-1] - mpp[lr[i][0]-1] )

#print(mpp)

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
d=[[0,0] for i in range(H*W+1)]
d2=[0 for i in range(H*W+1)]
for j in range(H):
  a=[int(x) for x in input().split()]
  for k in range(W):
    d[a[k]]=[j+1,k+1]
for l in range(D+1,H*W+1):
  d2[l]=abs(d[l][0]-d[l-D][0])+abs(d[l][1]-d[l-D][1])
for m in range(D+1,H*W+1):
  d2[m]+=d2[m-D]
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a==b:
    print(0)
  else:
    ans=d2[b]-d2[a]
    print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools
from pprint import pprint as pp

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

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

tbl = []
for i in range(D):
  ary = []
  mp = 0
  start = Arev[i+1]
  for x in range(i, H*W, D):
    next_ = Arev[x+1]
    mp += abs(start[0]-next_[0]) + abs(start[1]-next_[1])
    ary.append((x+1,mp))
    start = next_
  tbl.append(ary)
#pp(A)
#pp(tbl)
for L,R in LR:
  col1, row = divmod(L, D)
  col2 = R // D
  if row == 0:
    col1 -= 1
    col2 -= 1
  row -= 1
  #pp((row,col1,col2))
  print(tbl[row][col2][1] - tbl[row][col1][1])

Submission status: Accepted

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

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

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

keiro = [[0 for i in range(D)] for j in range(H * W // D + 1)]

for i in range(D, H * W):
    keiro[i // D][i % D] = mahou(Map[i + 1], Map[i + 1 - D]) + keiro[i // D - 1][i % D]
        
for l, r in LR:
    print(keiro[(r - 1) // D][(r - 1) % D] - keiro[(l - 1) // D][(l - 1) % D])

Submission status: Accepted

Solution code:
import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])

Submission status: Accepted

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

    f(H, W, D, A, Q, LR)


def f(H, W, D, A, Q, LR):
    """
    距離を計算しておく
    """
    pos = [None for _ in range(H * W + 1)]
    for y in range(H):
        for x in range(W):
            a = A[y][x]
            pos[a] = (x, y)

    d = [0 for _ in range(H * W + 1)]
    for i in range(1, D + 1):
        current = i
        dist = 0
        while current + D <= H * W:
            _next = current + D
            i, j = pos[current]
            x, y = pos[_next]

            dist += abs(x - i) + abs(y - j)

            # print((j, i), "to", (y, x), "cur", current, "next", _next, dist)
            d[_next] = dist
            current = _next

    # print(d)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

poss = [(0, 0)] * (H * W)
for i in range(H):
    for j in range(W):
        poss[As[i][j] - 1] = (i, j)

MPs = [[] for i in range(D)]
for st in range(1, D + 1):
    MPs[st - 1] += [0]
    pi, pj = poss[st - 1]
    for i, j in poss[st - 1 + D::D]:
        MPs[st - 1] += [MPs[st - 1][-1] + abs(i - pi) + abs(j - pj)]
        pi, pj = i, j

for L, R in LRs:
    st = (L - 1) % D + 1
    print(MPs[st - 1][(R - st) // D] - MPs[st - 1][(L - st) // D])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
 
A = [list(map(int, input().split())) for i in range(H)]
rA = [[0 for j in range(2)] for i in range(H * W + 1)]
S = [0 for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		rA[A[i][j]][0] = i
		rA[A[i][j]][1] = j
 
Q = int(input())
for i in range(Q):
	L, R = map(int, input().split())
	ans = 0
	for j in range(H * W) [L::D]:
		if j + D > H * W:
			break
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		if j + D > H * W:
			break
		S[j] += ans
	print(S[L] - S[R])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!A=int(input())

H,W,D=[int(i) for i in input().split()]
#AA=[]
KAZU=[0]*(H*W+1)
#print(KAZU)
for i in range(H):
#    AA=[int(i) for i in input().split()]
#    A.append(AA)
#    AA=[int(i) for i in input().split()]
    for (j, a) in enumerate(input().split()):
#        print(j,a)
        KAZU[int(a)] = [i,j] 

def cost(x, y):
    return abs(KAZU[x][0] -KAZU[y][0]) + abs(KAZU[x][1] -KAZU[y][1])

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


#print(KAZU)
Q=int(input())
for i in range(Q):
    l,r=[int(i) for i in input().split()]
    print(COSTMAT[r]-COSTMAT[l])

Submission status: Accepted

Solution code:
h, w, d = [int(x) for x in input().split()]
a = []
xy = [(0, 0)] * (h * w + 1)
for i in range(h):
  a.append([int(x) for x in input().split()])
  for j in range(w):
    xy[a[i][j]] = (i, j)
q = int(input())
L = []
R = []
for i in range(q):
  l, r = [int(x) for x in input().split()]
  L.append(l)
  R.append(r)

pw = [0] * (h * w + 1)
for i in range(1, d + 1):
  for j in range(d, h * w + 1, d):
    n = i + j
    p = n - d
    if n > h * w:
      break
    pw[n] = pw[p] + abs(xy[n][0] - xy[p][0]) + abs(xy[n][1] - xy[p][1])

for i in range(q):
  print(pw[R[i]] - pw[L[i]])

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
dist = [0]*(H*W+1)#dist[i]はiからi+Dまでの距離
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
    
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])

distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  distances[i%D]+=[dist[i]]
distances2 = [[0] for i in range(D)]#累積和に直す
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]

Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  l, r = (L-1)//D, (R-1)//D
  print(distances2[L%D][r]-distances2[L%D][l])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
branch = dict()
for i in range(1,h*w+1):
	branch[i] = []
for i in range(h):
	atemp = list(map(int,input().split()))
	for k in range(w):
		branch[atemp[k]].append(i+1)
		branch[atemp[k]].append(k+1)

q = int(input())
l = []
r = []
for i in range(q):
	ltemp,rtemp = map(int,input().split())
	l.append(ltemp)
	r.append(rtemp)

calc = dict()
for i in range(d):
	calc[i+1] = []
for i in range(1,d+1):
	now = i
	calc[i].append(0)
	k = 0
	while now+d <= h*w:
		calc[i].append(calc[i][k]+abs(branch[now][0]-branch[now+d][0])+abs(branch[now][1]-branch[now+d][1]))
		now = now+d
		k += 1

for i in range(q):
	div = l[i]//d
	if l[i]%d != 0:
		sur = l[i]%d
	else:
		sur = d
	ansdiv = r[i]//d
	if sur == d:
		print(calc[sur][ansdiv-1]-calc[sur][div-1])
	else:
		print(calc[sur][ansdiv]-calc[sur][div])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
H,W,D = map(int, input().split())

# Ah = np.array([0]*(H*W))
# Aw = np.array([0]*(H*W))
A = [0]*(H*W)
for h in range(H):
    As = list(map(int, input().split()))
    for w in range(W):
        A[As[w]-1] = (h,w)
    # Aw[As-1] = np.arange(W)
    # Ah[As-1] = h


Q = int(input())

# def solve(l, r):
#     ans = 0
#     # ah = Ah[l-1:r][::D]
#     # ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
#     # aw = Aw[l-1:r][::D]
#     # ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
#     ans = sum(Ah[l-1:l+D][::D])
#     while l != r:
#         x,y = A[l-1]
#         x2,y2 = A[l+D-1]
#         ans += abs(x-x2) + abs(y-y2)
#         l += D
#     return ans

Ans = [0]*(H*W)
aa = (H*W) // D
bb = (H*W) % D
for dth in range(1,aa+1):
    for d in range(D):
        if dth*D+d >=H*W:
            break
        x,y = A[(dth-1)*D+d]
        x2,y2 = A[dth*D+d]
        ans = abs(x-x2) + abs(y-y2)
        Ans[dth*D+d] = Ans[(dth-1)*D+d] + ans



lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(Ans[R-1] - Ans[L-1])
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
dist = [0]*(H*W+1)#dist[i]はiからi+Dまでの距離
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  d = dist[i]
  distances[i%D]+=[d]
distances2 = [[0] for i in range(D)]#累積和に直す
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(distances2[q][r]-distances2[q][l])

Submission status: Accepted

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = time[l] + (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return time[en-1] - time[st-1]


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[h,w,d]=i2()
a=[]
for i in range(h):
 s=i2()
 for j in range(w):
  a.append([s[j],[i,j]])
q=i1()
lr=[]
for i in range(q):
 lr.append(i2())
 
a=sorted(a)
f=[0 for i in range(h*w)]
for i in range(h*w-d):
  f[i+d]=f[i]+abs(a[i][1][0]-a[i+d][1][0])+abs(a[i][1][1]-a[i+d][1][1])

for i in lr:
 print(f[i[1]-1]-f[i[0]-1])

Submission status: Accepted

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

    MAP = {}
    for h in range(H):
        L = list(map(int, input().split()))
        for w in range(W):
            MAP[L[w]] = (h,w)


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

    Q = int(input())

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
a1=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
for i in range(h):
  i+=1
  tmp=list(map(int,input().split()))
  for j in range(w):
    num=tmp[j]
    j+=1
    a[num%d][int( (num-1)/d)]=[i,j]
for i in range(len(a)):
  a1[i][0]=0
  for j in range(len(a[i])-1):
    j=j+1
    if a[i][j]!=[]:
      a1[i][j]=a1[i][j-1]+abs(a[i][j][0]-a[i][j-1][0])+abs(a[i][j][1]-a[i][j-1][1])

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

Submission status: Accepted

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

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

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

Submission status: Accepted

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

cost = []
for i in range(h) :
    for j in range(w) :
        cost.append([A[i][j], j+1, i+1])

cost.sort(key=lambda c:c[0])


power = [0 for _ in range(h*w)]
for i in range(d) :
    pos = i
    x1 = cost[pos][1]
    y1 = cost[pos][2]
    while pos + d < h*w :
        x2 = cost[pos+d][1]
        y2 = cost[pos+d][2]
        power[pos+d] = power[pos] + abs(x1-x2) + abs(y1-y2)
        pos += d
        x1 = x2
        y1 = y2


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