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

masu=[]

for j in range(H):
  L=list(map(int,input().split()))
  for i in range(W):
    masu.append(tuple((L[i],j+1,i+1)))
masu=sorted(masu,key=lambda x:x[0])
#print(masu)

dp=[0]*(H*W)
#print(dp)

for i in range(D,H*W):
  dp[i]=dp[i-D]+abs(masu[i][1]-masu[i-D][1])+abs(masu[i][2]-masu[i-D][2])
#print(dp)

Q=int(input())

for _ 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())
A = [0] * H
for i in range(H):
  A[i] = list(map(int, input().split()))
dict = {}
for i in range(H):
  for j in range(W):
    dict[A[i][j]] = [i, j]

dp = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
  dp[k] = dp[k - D] + abs(dict[k][0] - dict[k - D][0]) + abs(dict[k][1] - dict[k - D][1])

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

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()

Submission status: Accepted

Solution code:
def main():
	H, W, D = map(int,input().split())
	pos = [0]*(H*W)
	for i in range(H):
		A = list(map(int, input().split()))
		for j in range(W):
			pos[A[j]-1] = [i, j]
	Q = int(input())
	lr = [0]*Q
	for i in range(Q):
		lr[i] = list(map(int, input().split()))
	ans = [[0] for _ in range(D)]
	for i in range(H*W-D):
		s_pos = pos[i]
		e_pos = pos[i+D]
		d = abs(s_pos[0]-e_pos[0])+abs(s_pos[1]-e_pos[1])
		ans[i%D].append(ans[i%D][-1]+d)
	for i in range(Q):
		s = lr[i][0]-1
		e = lr[i][1]-1
		print(ans[e%D][e//D]-ans[s%D][s//D])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

d = defaultdict(lambda:[])

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

cost = defaultdict(lambda:[0])
for r in range(1,D+1):
    for m in range(0,H*W//D):
        if D*(m+1)+r <= H*W:
            cost[r].append(abs(d[D*m+r][0]-d[D*(m+1)+r][0])+abs(d[D*m+r][1]-d[D*(m+1)+r][1]))
for r in range(1,D+1):
    for m in range(len(cost[r])-1):
        cost[r][m+1] += cost[r][m]

Q = int(input())

def magic(L,R):
    r = L%D
    if r == 0:
        r = D
    ml = (L-r)//D
    mr = (R-r)//D
    return cost[r][mr]-cost[r][ml]


for _ in range(Q):
    L,R = map(int,input().split())
    print(magic(L,R))

Submission status: Accepted

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

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

ans = [0]*(H*W)
for i in range(D):
    bl = tmp[i][0]
    br = tmp[i][1]
    i += D
    zp = 0
    while i < H*W:
        l = tmp[i][0]
        r = tmp[i][1]
        ans[i] = abs(bl-l)+abs(br-r)+zp
        zp = ans[i]
        bl = l
        br = r
        i += D

jjj = []
for _ in range(Q):
    L,R = [int(i) for i in input().split()]
    jjj.append(ans[R-1]-ans[L-1])

[print(i) for i in jjj]

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
a_array = [[int(x) for x in input().split()] for y in range(h)]
q = int(input())
lr_array = [[int(x) for x in input().split()] for y in range(q)]

whole = []
for i in range(h):
    for j in range(w):
        whole.append([a_array[i][j], i + 1, j + 1])
whole = [[x[1], x[2]] for x in sorted(whole, key=lambda x: x[0])]
diff = [0 for x in range(h * w)]
for i in range(d, h * w):
    if diff[i] != 0:
        continue
    if i == 0:
        continue
    for j in range(i, h * w, d):
        base_x, base_y = whole[j]
        next_x, next_y = whole[j-d]
        diff[j] = diff[j-d]+abs(base_x - next_x) + abs(base_y - next_y)

for l, r in lr_array:
    print(diff[r-1]-diff[l-1])

Submission status: Accepted

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

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


ru = {}
for i in range(1,D+1):
    ru[i] = [0]

for i in range(1,D+1):
    c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1

for i in range(Q):
    t = LR[i][0] % D
    if t == 0:
        t = D
        print(ru[t][LR[i][1]//D-1] - ru[t][LR[i][0]//D-1])
    else:
        print(ru[t][LR[i][1]//D] - ru[t][LR[i][0]//D])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
d_x = [-1] * (h*w + 1)
d_y = [-1] * (h*w + 1)
for i in range(h):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        d_x[tmp[j]] = i
        d_y[tmp[j]] = j

dist = [-1] * (h*w + 1) 
for i in range(h*w):
    j = h*w - i
    if h*w - j < d:
        dist[j] = 0
    else:
        dist[j] = dist[j+d] + abs(d_x[j+d] - d_x[j]) + abs(d_y[j+d] - d_y[j])
    
q =  int(input())
for _ in range(q):
    start, end = map(int, input().split())
    print(dist[start]- dist[end])

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


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


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    a, q, lr = aqlr[:h * w], aqlr[h * w], aqlr[h * w + 1:]
    n = h * w
    pos = [0] * (n + 1)
    for i, _a in enumerate(a):
        pos[_a] = (i // w, i % w)
    cost = [0] * (n + 1)
    for i in range(d + 1, n + 1):
        cost[i] = cost[i - d] + distance(pos[i - d], pos[i])
    return "\n".join(["%d" % (cost[r] - cost[l]) for l, r in chunked(lr, 2)])


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


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


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    a, q, lr = aqlr[:h * w], aqlr[h * w], aqlr[h * w + 1:]
    n = h * w
    pos = [0] * (n + 1)
    for i, _a in enumerate(a):
        pos[_a] = (i // w, i % w)
    cost = [0] * (n + 1)
    for i in range(d + 1, n + 1):
        cost[i] = cost[i-d]+distance(pos[i - d], pos[i])
    ans = []
    for l, r in chunked(lr, 2):
        ans.append("%d" % (cost[r] - cost[l]))
    return "\n".join(ans)


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Submission status: Accepted

Solution code:
import sys
fastinput = sys.stdin.readline
H,W,D = [int(_) for _ in input().split()]
row=((H*W)//D+1)
modD = [[(0,0)]*row for i in range(D)] #modD[x][y]:x(modD)の数で商がyのやつの位置のタプル
for h in range(H):#0-indexed(0<=h<=H-1)
    A=[int(__) for __ in fastinput().split()]
    for w,a in enumerate(A):#めんどくさいのでマスの数も座標も0-indexed
        y,x = (a-1)//D,(a-1)%D
        modD[x][y]=(h,w)
costs=[[0]*row for i in range(D)]#コストの累積和
for d in range(D):
    pre=(0,0)
    curcos=0
    for k in range(row):
        now=modD[d][k]
        curcos += abs(now[0]-pre[0]) + abs(now[1]-pre[1])
        costs[d][k]=curcos
        pre=now
Q=int(input())
for _ in range(Q):
    s,g=[int(i)-1 for i in fastinput().split()]
    amari=s%D
    sRow,gRow=s//D,g//D
    print(costs[amari][gRow]-costs[amari][sRow])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = [0]*(H*W+1)
for i in range(H):
    a = list(map(int,input().split()))
    for j in range(W):
        A[a[j]] = (i,j)
d = [0]*(H*W+1)
for i in range(D+1,H*W+1):
    d[i] = d[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[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:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

H, W, D = l_inpl()
A = {}

for hi in range(H):
    l = l_inpl()
    for wi in range(W):
        A[l[wi]] = [wi, hi]

Q = i_inpl()
LR = []
for _ in range(Q):
    LRi = l_inpl()
    LR.append(LRi)

power = []
for i in range(1, H*W-D+1):
    power.append(abs(A[i+D][0] - A[i][0]) + abs(A[i+D][1] - A[i][1]))
    
r_cumsum = [0] * D
for i in range(len(power)):
    r_cumsum.append(r_cumsum[i] + power[len(power)-i-1])

cumsum = r_cumsum[::-1]

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

Submission status: Accepted

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

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
        
number = [0 for _ in range(H*W+1)]
for i in range(H*W):
    now = H * W - i
    
    if now + D > H * W:
        pass
    
    else:
        number[now] = number[now + D] + abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
       

for i in range(Q):
    res = number[LR[i][0]] - number[LR[i][1]]
            
    print(res)

Submission status: Accepted

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


def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pieces = [0] * (h * w + 1)
    cost = [0 for _ in range(h * w + 1)]

    for hi in range(h):
        for wi in range(w):
            number = a[hi][wi]
            pieces[number] = (hi, wi)

    # See:
    # https://img.atcoder.jp/abc089/editorial.pdf
    # https://www.youtube.com/watch?v=EDq1rl-6YcQ
    for i in range(d + 1, h * w + 1):
        prev_piece = pieces[i - d]
        next_piece = pieces[i]

        cost[i] = cost[i - d] + \
            abs(next_piece[1] - prev_piece[1]) + \
            abs(next_piece[0] - prev_piece[0])

    q = int(input())
    ans = [0 for _ in range(q)]

    for j in range(q):
        lj, rj = map(int, input().split())
        ans[j] = cost[rj] - cost[lj]

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)

sum_list = []

for i in range(1,d+1):
	temp_list = []
	left = i
	s = 0
	for j in range(i,w*h+1,d):
		s +=  manhattan(grid_list[left-1],grid_list[j-1])
		temp_list.append(s)

		left = j
	sum_list.append(temp_list)

m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	print(sum_list[r%d-1][(r-1)//d]-sum_list[l%d-1][(l-1)//d])

Submission status: Accepted

Solution code:
from operator import itemgetter

H,W,D = [int(x) for x in input().split()]
a = []

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]
#%%
stims = [[[0,0,0]]for _ in range(D)]
dinds = [{}for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d][i[0]]=len(stims[d])-1

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum][i[0]]
    r = dinds[dnum][i[1]]
    print(stims[dnum][r][0]-stims[dnum][l][0])

Submission status: Accepted

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

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

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

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

Q = int(input())

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

DS = [[0] for i in range(D)]
for i in range(D):
    ds = 0
    j=1
    while j*D + i <H*W:
        ds+=abs(B[j*D + i][0]-B[(j-1)*D + i][0])+abs(B[j*D + i][1]-B[(j-1)*D + i][1])
        DS[i].append(ds)
        j+=1

for i in range(Q):
    l,r=C[i]
    l=l-1
    r=r-1
    q=l%D
    print(DS[q][r//D]-DS[q][l//D])

Submission status: Accepted

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

sumL=[0 for i in range(h*w+1)]
for i in range(h*w):
  if i>=d:
    sumL[i+1]=sumL[i+1-d]+abs(L[i][0]-L[i-d][0])+abs(L[i][1]-L[i-d][1])

q=int(input())
QL=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(sumL[QL[i][1]]-sumL[QL[i][0]])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
MAP=[list(map(int,input().split())) for i in range(H)]
Q=int(input())
data=dict()
from collections import defaultdict
cost=defaultdict(int)
for i in range(H):
    for j in range(W):
        data[MAP[i][j]]=(i,j)
for i in range(1,D+1):
    bef=i
    now=i
    c=0
    cost[i]=0
    while now+D<=H*W:
        bef,now=now,now+D
        c+=abs(data[now][0]-data[bef][0])+abs(data[now][1]-data[bef][1])
        cost[now]=c
def solve():
    L,R=map(int,input().split())
    return cost[R]-cost[L]
for q in range(Q):
    print(solve())

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
d = [[0,0,0] for _ in range(H*W+2)]
for h in range(H):
    for w in range(W):
        d[A[h][w]+1] = [h+1,w+1,0]
d = d[2:]
for i in range(H*W):
    if i < D:
        continue
    d[i][2] = d[i-D][2]+abs(d[i][0]-d[i-D][0])+abs(d[i][1]-d[i-D][1])
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(d[r-1][2]-d[l-1][2])

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


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

cost_sum = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(d):
    for j in range(int(math.ceil(h * w / d))):
        if j != 0:
            cost_sum[i][j] = cost_sum[i][j-1] + cost[i][j-1]
        else:
            cost_sum[i][j] = 0

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1

    _cost_sum = cost_sum[int(l % d)]
    print(_cost_sum[int(r / d)] - _cost_sum[int(l / d)])

Submission status: Accepted

Solution code:

from collections import defaultdict


def main():
    high, width, d = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(high)]

    land_dic = defaultdict(tuple)
    for i in range(high):
        for j in range(width):
            num = data[i][j]
            land_dic[num] = (i, j)

    dp = [0 for i in range(high * width + 1)]
    for i in range(d + 1, high * width + 1):
        now_num = i
        pre_num = i - d
        now_place = land_dic[now_num]
        pre_place = land_dic[pre_num]
        dist = abs(now_place[0] - pre_place[0]) + abs(now_place[1] - pre_place[1])
        dp[i] = dp[i - d] + dist

    q_num = int(input())
    for i in range(q_num):
        start, goal = map(int, input().split())
        print(dp[goal] - dp[start])





if __name__ == '__main__':
    main()

Submission status: Accepted

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

C = [0] * (H * W)
for i in range(D, H * W):
    h, w = B[i - D]
    nh, nw = B[i]
    C[i] = C[i - D] + abs(nh - h) + abs(nw - w)

Q = int(input())
for l, r in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
    print(C[r] - C[l])

Submission status: Accepted

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t={}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    ans=[0]*(h*w+1)
    for i in range(h*w,d,-1):
        o,p=t[i]
        ans[i-d]=ans[i]+abs(o-t[i-d][0])+abs(p-t[i-d][1])
    q=int(input())
    for i in range(q):
        l,r=map(int,input().split())
        print(ans[l]-ans[r])

if __name__=="__main__":
    sol()

Submission status: Accepted

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

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

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

answers = [[] for _ in range(D)]
d_length = (H * W) // D + 1
for d in range(D):
    current = d
    d_answers = [0 for _ in range(d_length)]
    idx = 1
    while current + D < H * W:
        d_answers[idx] = get_distance(current, current+D) + d_answers[idx-1]
        current += D
        idx += 1
    answers[d] = d_answers

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

Submission status: Accepted

Solution code:
h, w, d = map(int,input().split())
a = [list(map(int,input().split()))for _ in range(h)]
pos = dict()
for i in range(h):
  for j in range(w):
    pos[a[i][j] - 1] = (i, j)
dis = [[0] for _ in range(d)]
for i in range(d):
  num = i
  while num < h * w - d:
    p = pos[num]
    nextp = pos[num + d]
    dis[i - 1].append(abs(nextp[0] - p[0]) + abs(nextp[1] - p[1]))
    num += d
for i in range(d):
  for j in range(len(dis[i])-1):
    dis[i][j + 1] += dis[i][j]
q = int(input())
for i in range(q):
  l, r = map(lambda x:int(x)-1, input().split())
  print(dis[l % d - 1][r // d] - dis[l % d - 1][l // d])

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
  tmp=list(map(int,input().split()))
  for j in range(w):
    pos[tmp[j]]=[i+1,j+1]
cs=[[0] for _ in range(k+1)]
for i in range(1,k+1):
  for j in range(1,(h*w-i)//k+1):
    x1,y1=pos[i+k*(j-1)][1],pos[i+k*(j-1)][0]
    x2,y2=pos[i+k*j][1],pos[i+k*j][0]
    cs[i].append(abs(y2-y1)+abs(x2-x1)+cs[i][j-1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  tmp=l%k
  if tmp==0:
    tmp=k
  l,r=(l-tmp)//k,(r-tmp)//k
  print(cs[tmp][r]-cs[tmp][l])

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


def main():
    h, w, d = intin()
    alistlist = []
    for i in range(h):
        alistlist.append(intina())
    q = intin()
    lrlist = intinl(q)

    blist = {0: (0, 0)}
    for i, alist in enumerate(alistlist):
        for j, a in enumerate(alist):
            blist[a] = (i, j)

    slistlist = []
    hwmax = h * w

    for i in range(d):
        slist = [0]
        a = i
        magicsum = 0
        while True:
            anext = a + d
            if anext > hwmax:
                break
            magicsum += abs(blist[a][0] - blist[anext][0]) + \
                        abs(blist[a][1] - blist[anext][1])
            slist.append(magicsum)
            a = anext
        slistlist.append(slist)

    for l, r in lrlist:
        slist = slistlist[l % d]
        print(slist[r // d] - slist[l // d])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    D = int(buflist[2])
    board = []
    for i in range(H):
        buf = input()
        buflist = buf.split()
        board.append(list(map(int, buflist)))
    buf = input()
    Q = int(buf)
    query = []
    for i in range(Q):
        buf = input()
        buflist = buf.split()
        L = int(buflist[0])
        R = int(buflist[1])
        query.append((L, R))
    moddivxy = []
    for i in range(H):
        for j in range(W):
            moddivxy.append((board[i][j] % D, board[i][j] // D, i, j))
    moddivxy = list(sorted(moddivxy))
    mp_table = [[0]]
    mod = 0
    last_xy = (-1, -1)
    for x in moddivxy:
        if x[0] == 0 and x[1] == 1: # first element
            mp_table[mod].append(0)
        elif x[0] > mod:
            mod = x[0]
            mp_table.append([0])
        else:
            mp_table[mod].append(mp_table[mod][-1] + abs(last_xy[0] - x[2]) + abs(last_xy[1] - x[3]))
        last_xy = (x[2], x[3])
    for q in query:
        m = q[0] % D
        d_start = q[0] // D
        d_end = q[1] // D
        print(mp_table[m][d_end] - mp_table[m][d_start])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,D = list(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)]

X = [None]*(H*W+1) #X[i]:iが書かれたマスの座標
for h, row in enumerate(A):
  for w, a in enumerate(row):
    #A[h][w] = A_h+1_w+1
    X[a] = (h+1,w+1)

Y = [0]*(H*W+1) #X[i]: X[d]からDごとの系列で移動してきた移動量の和
for d in range(1,D+1):
  x = d
  while x+D <= H*W:
    Y[x+D] = Y[x] + abs(X[x+D][0]-X[x][0]) + abs(X[x+D][1]-X[x][1])
    x+=D

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

Submission status: Accepted

Solution code:

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

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

for i in range(H):
    a=list(map(int,input().split()))
    for j in range(W):
        mp[a[j]]=[i,j]
S = []
for i in range(1,D+1):
    s1 = [0]
    s2 = 0
    j=1
    while j*D+i<=H*W:
        s2+=abs(mp[j*D+i][0]-mp[(j-1)*D+i][0])+abs(mp[j*D+i][1]-mp[(j-1)*D+i][1])
        s1.append(s2)
        j+=1
    S.append(s1)
ans=[]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    d=(L-1)%D
    e=(R-1)//D
    f=(L-1)//D
    ans.append(S[d][e]-S[d][f])
    
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
n=0
h,w,d=map(int,input().split())
x=[0]*(h*w)
y=[0]*(h*w)
for i in range(h):
    for a in input().split():
        A=int(a)-1
        x[A]=n%w
        y[A]=n//w
        n+=1
        
c=[0]*(h*w)
for i in range(h*w):
    if i>=d:
        c[i]=c[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W
ND = N//D

# 各数値の書かれている位置, 1-indexed
X = np.zeros((D,ND+1),dtype=np.int64)
Y = np.zeros((D,ND+1),dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    n = int(n)
    q,r = n//D,n%D
    X[r,q] = x
    Y[r,q] = y

# 0D+d から nD+d への移動コスト
MAGIC = np.zeros_like(X)
MAGIC[:,1:] = (np.abs(np.diff(X,axis = 1)) + np.abs(np.diff(Y,axis = 1))).cumsum(axis = 1)

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  d = l%D
  print(MAGIC[d,r//D] - MAGIC[d,l//D])

Submission status: Accepted

Solution code:
from itertools import*
from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
f=defaultdict(int)
for i in range(h):
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
        
q=int(input())

for i in range(1,d+1):
    for k,v in enumerate(accumulate([0]+[sum(abs(s-t)for s,t in zip(g[j+d],g[j]))for j in range(i,h*w+1-d,d)])):
        f[i+k*d]=v
        
for i in range(q):
    l,r=map(int,input().split())
    print(f[r]-f[l])

Submission status: Accepted

Solution code:
#coding:utf-8
H,W,D=map(int,raw_input().split())
A=[None]
for i in range(H):
    b=map(int,raw_input().split())
    A.append([None]+b)
Q=int(raw_input())
L=[];R=[]
for i in range(Q):
    l,r=map(int,raw_input().split())
    L.append(l);R.append(r)

P={}
for i in range(1,H+1):
    for j in range(1,W+1):
        P[A[i][j]]=(i,j)
C={}
for d in range(1,D+1):
    x=d
    cost=0
    C[d]=0
    while x+D<=H*W:
        n=x+D
        np=P[n];pp=P[x]
        distance=abs(np[0]-pp[0])+abs(np[1]-pp[1])
        cost+=distance
        C[n]=cost
        x=n
for l,r in zip(L,R):
    print(C[r]-C[l])