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:
dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
n = h * w
su = [0] * (n + 1)
for k in range(1, n - d + 1):
    x = dic[k + d][0] - dic[k][0]
    y = dic[k + d][1] - dic[k][1]
    su[k + d] = su[k] + abs(x) + abs(y)

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

Submission status: Accepted

Solution code:
import pprint
H,W,D=map(int,input().split())
table=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
query=[list(map(int,input().split())) for _ in range(Q)]
num=[]
distfrom1D=[]
cumldist=[0]*(H*W+1)
for i in range(H):
    for j in range(W):
        num.append([table[i][j],i,j])
num.sort(key=lambda x:x[0])
#print(num)
#for i in range()
cnt=0
"""
for i in range(D):
    buf=[0]
    for j in range(i,H*W-D,D):
        #print(i+j,i+j+D)
        buf.append(buf[len(buf)-1]+abs(num[j][1]-num[j+D][1])+abs(num[j][2]-num[j+D][2]))
    #print(buf)
    distfrom1D.append(buf)
#[1,1+D,]
#[2,2+D,]
#...
#[D,D+D,]
#pprint.pprint(distfrom1D)
for i in range(Q):
    l=query[i][0]
    r=query[i][1]
    row=((l%D)-1)%D
    col1 = (l // D)
    col2 = (r // D)
    if l%D==0:
        col1=col1-1
        col2=col2-1
    print(distfrom1D[row][col2]-distfrom1D[row][col1])
"""
#""l-r%D==0より""、各点考えられる固定の始点(1..D)から1,2,...,1+D,2+D,...,1+2D,2+2D,...の累積和をdpっぽく作れる
for i in range(1,H*W+1):
    if i//D>0:
        cumldist[i]=cumldist[i-D]+abs(num[i-D-1][1]-num[i-1][1])+abs(num[i-D-1][2]-num[i-1][2])
#print(cumldist)
for i in range(Q):
    l=query[i][0]
    r=query[i][1]
    print(cumldist[r]-cumldist[l])

Submission status: Accepted

Solution code:
import pprint
H,W,D=map(int,input().split())
table=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
query=[list(map(int,input().split())) for _ in range(Q)]
num=[]
distfrom1D=[]
for i in range(H):
    for j in range(W):
        num.append([table[i][j],i,j])
num.sort(key=lambda x:x[0])
#print(num)
#for i in range()
cnt=0
for i in range(D):
    buf=[0]
    for j in range(i,H*W-D,D):
        #print(i+j,i+j+D)
        buf.append(buf[len(buf)-1]+abs(num[j][1]-num[j+D][1])+abs(num[j][2]-num[j+D][2]))
    #print(buf)
    distfrom1D.append(buf)
#[1,1+D,]
#[2,2+D,]
#...
#[D,D+D,]
#pprint.pprint(distfrom1D)
for i in range(Q):
    l=query[i][0]
    r=query[i][1]
    row=((l%D)-1)%D
    col1 = (l // D)
    col2 = (r // D)
    if l%D==0:
        col1=col1-1
        col2=col2-1
    print(distfrom1D[row][col2]-distfrom1D[row][col1])

Submission status: Accepted

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

board_dic={}
for i in range(H):
  array=list(map(int,input().split()))
  for j in range(W):
    num=array[j]
    board_dic[num]=(i+1,j+1)
#print(board_dic)  
  
dslist=[]
for i in range(1,D+1):
  dl=[0]
  for j in range(i+D,H*W+1,D):
    x1,y1=board_dic[j-D]
    x2,y2=board_dic[j]
    dist=abs(x2-x1)+abs(y2-y1)
    dl.append(dl[-1]+dist)
  dslist.append(dl)
#print(dslist)    

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

Submission status: Accepted

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

board_dic={}
for i in range(H):
  array=list(map(int,input().split()))
  for j in range(W):
    num=array[j]
    board_dic[num]=(i+1,j+1)
#print(board_dic)  
  
dslist=[]
for i in range(1,D+1):
  dl=[0]
  for j in range(1,10**9):
    if i+j*D>H*W:
      break
    x1,y1=board_dic[i+(j-1)*D]
    x2,y2=board_dic[i+j*D]
    dist=abs(x2-x1)+abs(y2-y1)
    dl.append(dl[-1]+dist)
  dslist.append(dl)
#print(dslist)    

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

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

from collections import defaultdict
zahyo = defaultdict(list)
for i in range(h):
    for j in range(w):
        zahyo[a[i][j]-1] = [i,j]

rui=[0]*(h*w + 10)
for i in range(d,h*w):
    last=zahyo[i-d]
    now = zahyo[i]

    dist = abs(last[0]-now[0]) + abs(last[1]-now[1])
    rui[i] = rui[i-d] + dist

for que in lr:
    l,r=que
    print(rui[r-1]-rui[l-1])

Submission status: Accepted

Solution code:
def main():
  h, w, d = map(int, input().split())
  a = [list(map(int, input().split())) for i in range(h)]
  pts = [(0, 0) for i in range(h * w)]
  for i in range(h):
    for j in range(w):
      a[i][j] -= 1
      pts[a[i][j]] = (i, j)
  c = [[0 for j in range(h * w // d + 10)] for i in range(d)]
  for s in range(d):
    i = s
    j = s + d
    while j < h * w:
      iy, ix = pts[i]
      jy, jx = pts[j]
      c[s][(j - j % d) // d] = c[s][(i - i % d) // d] + abs(iy - jy) + abs(ix - jx)
      i += d
      j += d
  q = int(input())
  for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    s = l % d
    print(c[s][(r - r % d) // d] - c[s][(l - l % d) // d])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc089/tasks/abc089_d
# 17:17-18:17 read testcase
# 18:17-18:26 done


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L, R = [None] * Q, [None] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())
        L[i] -= 1  # 1-index => 0-index
        R[i] -= 1  # 1-index => 0-index
    
    if D == H*W:
        for _ in range(Q):
            print(0)
        return None

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

    n_graph = D if D <= (H*W)//2 else (H*W)-D

    graphs = [[] for _ in range(n_graph)]

    for start in range(n_graph):
        cost = 0
        start_x, start_y = positions[start]
        m = 0
        while start + m*D < H*W:
            to_x, to_y = positions[start + m*D]
            cost += abs(to_x-start_x) + abs(to_y-start_y)
            graphs[start].append(cost)
            start_x, start_y = to_x, to_y
            m += 1

    for l, r in zip(L, R):
        graph_num = l % n_graph
        graph = graphs[graph_num]
        print(graph[r//D] - graph[l//D])


main()
# print(main())

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
C = [None] * (H * W + 1)
for h in range(H):
    m = map(int, input().split())
    for w, x in enumerate(m):
        C[x] = (h, w)

Acc = [[0] for _ in range(D)]
for i in range(D):
    x = i + 1
    while x + D <= H * W:
        Acc[i].append(Acc[i][-1] + abs(C[x + D][0] - C[x][0]) + abs(C[x + D][1] - C[x][1]))
        x += D

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

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

N = H*W

B = [0]*(N+1)
for h in range(H):
    for w in range(W):
        n = A[h][w]
        B[n] = (h,w)

C = [[0 for _ in range((H*W)//D+1)]for _ in range(D)]
for i in range(D+1,N+1):
    rem = i%D
    x0,y0 = B[i-D]
    x1,y1 = B[i]
    C[rem][i//D] = abs(x1-x0) + abs(y1-y0)

for i in range(D):
    for j in range(1,(H*W)//D+1):
        C[i][j] += C[i][j-1]

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    zahyou = [[] for _ in range(d)]
    for x in range(h):
        for y in range(w):
            b = a[x][y] % d
            zahyou[b].append([a[x][y], x, y])

    mp = [[] for _ in range(d)]
    for i in range(d):
        xy = zahyou[i]
        xy.sort()
        mp[i].append(0)
        cx, cy = xy[0][1:]
        for j in range(1, len(xy)):
            mp[i].append(abs(xy[j][1]-cx)+abs(xy[j][2]-cy))
            cx, cy = xy[j][1:]
        mp[i] = list(accumulate(mp[i]))
    
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        amari = l % d
        l = (l-1) // d
        r = (r-1) // d
        print(mp[amari][r] - mp[amari][l])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def cost(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


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

    dist = {}
    for i in range(1, d + 1):
        dist[i] = {i: 0}
        nxt = i + d
        while nxt <= h * w:
            dist[i][nxt] = dist[i][nxt - d] + cost(pos[nxt - d], pos[nxt])
            nxt += d
    
    q = int(input())
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        base = l % d
        if base == 0:
            base = d
        ans.append(dist[base][r] - dist[base][l])
        
    for a in ans:
        print(a)


submit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

for i in range(H):
    for j in range(W):
        xd[A[i][j]] = i
        yd[A[i][j]] = j

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

for i in range(D+1, H*W+1):
    cost = abs(xd[i]-xd[i-D])+abs(yd[i]-yd[i-D])
    acc[i%D].append(acc[i%D][-1]+cost)
    
Q = int(input())

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

Submission status: Accepted

Solution code:
from collections import *

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

for i in range(H):
    for j in range(W):
        xd[A[i][j]] = i
        yd[A[i][j]] = j

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

for i in range(D+1, H*W+1):
    cost = abs(xd[i]-xd[i-D])+abs(yd[i]-yd[i-D])
    acc[i%D].append(acc[i%D][-1]+cost)
    
Q = int(input())

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

Submission status: Accepted

Solution code:
from collections import *

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

for i in range(H):
    for j in range(W):
        xd[A[i][j]] = i
        yd[A[i][j]] = j

arr = [[] for _ in range(D)]

for i in range(D+1, H*W+1):
    arr[i%D].append(abs(xd[i]-xd[i-D])+abs(yd[i]-yd[i-D]))

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

for i in range(D):
    for j in range(len(arr[i])):
        acc[i].append(acc[i][-1]+arr[i][j])
    
Q = int(input())

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

Submission status: Accepted

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

pos_x = [None]*(h*w)
pos_y = [None]*(h*w)
for i in range(h):
    a_list = list(map(int,input().split()))
    for j,a in enumerate(a_list):
        pos_x[a-1] = j
        pos_y[a-1] = i

power = [0]*(h*w)
for i in range(h*w):
    if i<d:
        continue
    else:
        use = abs(pos_x[i]-pos_x[i-d]) + abs(pos_y[i]-pos_y[i-d])
        power[i] = power[i-d] + use

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

Submission status: Accepted

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

# 番号→座標のテーブル作成
for i in range(H):
  AA = list(map(int,input().split()))
  for j in range(W):
    A[AA[j]-1][0] = i
    A[AA[j]-1][1] = j

# %D が同じ値のグループごとに累積和
M = [0] * (H*W)
for d in range(D):
  i = 1
  while (D * i + d) < (H*W) :
    pn = D * (i-1) + d
    n = D * i + d
    M[n] = M[pn] + abs(A[n][0] - A[pn][0]) + abs(A[n][1] - A[pn][1])
    i += 1

# 累積和をみて回答
Q = int(input())
for i in range(Q):
  L,R=map(int,input().split())
  print( M[R-1] - M[L-1] )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline


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

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

    A = [[0] for j in range(D)]

    for i in range(D):
        accumu = 0
        for j in range(i, H * W + 1, D):
            if j <= D:
                continue
            accumu += abs(d[j][0] - d[j - D][0]) + abs(d[j][1] - d[j - D][1])
            A[i].append(accumu)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
H, W, D = map(int, input().split())
def dist(x, y):
    return abs(x[0]-y[0]) + abs(x[1]-y[1])
X = []
for _ in range(H):
    X.append(list(map(int, input().split())))

d = dict()
for i in range(H):
    x = X[i]
    for j in range(W):
        d[x[j]] = (i, j)
Ls = []
for i in range(1, D+1):
    tmp = [0]
    st = d[i]
    j = i
    while j in d:
        tmp.append(tmp[-1]+dist(st, d[j]))
        st = d[j]
        j += D
    Ls.append(tmp)

Q = int(input())
for _ in range(Q):
    x, y = map(int, input().split())
    a, b = divmod(x, D)
    c, d = divmod(y, D)
    if b > 0:
        print(Ls[b-1][c+1]-Ls[b-1][a+1])
    else:
        print(Ls[b-1][c]-Ls[b-1][a])

Submission status: Accepted

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

h, w, d = [int(x) for x in input().split()]
a = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lr = [[int(x) for x in input().split()] for _ in range(q)]

dic = {}

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

dis = {}

for i in range(1, d + 1):
    dis[i] = 0
    while i + d <= h * w:
        dis[i + d] = dis[i] + abs(dic[i + d][0] - dic[i][0]) + abs(dic[i + d][1] - dic[i][1])
        i += d

for i in range(q):
    l, r = lr[i]
    print(dis[r] - dis[l])

Submission status: Accepted

Solution code:
import io
import math

I=lambda:map(int,input().split())

h,w,d=I()

H={}

W={}

for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
    
x=1+h*w
s=[0 for _ in [0]*x]

for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

for _ in [0]*int(input()):
  a,b=I()
  print(s[b]-s[a])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W, D = iip()

    A = iipt(H)
    Q = iip(False)
    LR = iipt(Q)

    position = [None for i in range(H*W)]
    for i in range(H):
       for j in range(W):
           n = A[i][j]
           position[n-1] = (i, j)

    distanse = [None] * (H*W)
    for i in range(H*W):
        if distanse[i] is None:
            distanse[i] = 0
        if i+D >= H*W:
            continue
        distanse[i+D] = distanse[i] + abs(position[i][0]-position[i+D][0]) + abs(position[i][1]-position[i+D][1])

    #print(distanse)
    for l, r in LR:
         l -= 1
         r -= 1
         print(distanse[r]-distanse[l])


#####################################################ライブラリ集ここから

def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])

Submission status: Accepted

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

def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(h)]
    loc = [None for i in range(h * w + 1)]
    for i in range(h):
        for j in range(w):
            loc[a[i][j]] = (i, j)

    f = [None for i in range(h * w + 1)]
    for x0 in range(h * w):
        x1 = x0 + 1
        if x1 <= d:
            f[x1] = 0
        else:
            r1, l1 = loc[x1]
            r2, l2 = loc[x1 - d]
            f[x1] = f[x1 - d] + abs(r1 - r2) + abs(l1 - l2)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

bit = [0]*n
for i in range(n):
  if i < d:
    continue
  bit[i] = bit[i-d]+abs(place[i][0]-place[i-d][0])+abs(place[i][1]-place[i-d][1])

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

Submission status: Accepted

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

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

#print(pos)

for i in range(h*w):
    #print(i//h,i%w)
    #print(aij[i//w][i%w])
    pos[aij[i//w][i%w]] = [i//w,i%w]
    #pos.append([aij[i//h][i%w]])
 
#print(pos)
#exit()

rui = [0] * (h*w+1)
#print(pos[1])
tmp = 0

for j in range(d+1,h*w+1):
    #print(j,pos[j-d])
    rui[j] = rui[j-d] + abs(pos[j][0] - pos[j-d][0]) + abs(pos[j][1] - pos[j-d][1])
    """
    if j + d <= h*w:
        tmp += abs(pos[j][0] - pos[j+d][0]) + abs(pos[j][1] - pos[j+d][1])
        rui.append(tmp)
    else:
        break
    #pos[i][0])
    #rui.append()
    """
for i in range(q):
    print(rui[lr[i][1]]-rui[lr[i][0]])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w,d = m()

dp = [[0,0] for i in range(h*w+1)]

cost = [0 for i in range(h*w+1)]

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

for i in range(1,d+1):
    co = i
    while True:
        if co+d > h*w:
            break
        cost[co+d] = cost[co] + abs(dp[co+d][0] - dp[co][0]) + abs(dp[co+d][1] - dp[co][1])
        co += d

n = onem()

for i in range(n):
    L,R = m()
    print(abs(cost[R]-cost[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={}
for i in range(h):
  for j in range(w):
    dic[a[i][j]]=(i,j)
cnt=[0]*(h*w+1)
for j in range(1,d+1):
  for i in range(j,h*w-d+1,d):
    y1,x1=dic[i+d]
    y2,x2=dic[i]
    cnt[i+d]=cnt[i]+abs(x2-x1)+abs(y2-y1)
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[ list(map(int,input().split())) for _ in range(h) ]
q=int(input())
cost=[0 for _ in range(h*w+1)]
pos=dict()
l=[]
for i in range(h):
    for j in range(w):
        pos[a[i][j]]=[i,j]
        l.append((a[i][j],i,j))
l.sort()
for val,x,y in l:
    if val-d<=0:
        cost[val]=0
    else:
        cost[val]=cost[val-d]+abs(pos[val][0]-pos[val-d][0])+abs(pos[val][1]-pos[val-d][1])
#print(l)
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=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
X=[[0,0] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        X[A[i][j]][0]=i
        X[A[i][j]][1]=j
M=[0]*(H*W+1)
for d in range(D+1,H*W+1):
        M[d]=abs(X[d][0]-X[d-D][0])+abs(X[d][1]-X[d-D][1])+M[d-D]

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
X=[[[0,0] for _ in range((H*W)//D+1)] for _ in range(D)]
for i in range(H):
    for j in range(W):
        X[A[i][j]%D][A[i][j]//D][0]=i
        X[A[i][j]%D][A[i][j]//D][1]=j
M=[[0]*((H*W)//D+1) for _ in range(D)]
for d in range(D):
    for k in range((H*W)//D):
        M[d][k+1]=abs(X[d][k+1][0]-X[d][k][0])+abs(X[d][k+1][1]-X[d][k][1])+M[d][k]

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

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())
X=[[[0,0] for _ in range((H*W)//D+1)] for _ in range(D)]
for i in range(H):
    for j in range(W):
        X[A[i][j]%D][A[i][j]//D][0]=i
        X[A[i][j]%D][A[i][j]//D][1]=j
M=[[0] for _ in range(D)]
for d in range(D):
    for k in range((H*W)//D):
        M[d].append(abs(X[d][k+1][0]-X[d][k][0])+abs(X[d][k+1][1]-X[d][k][1])+M[d][k])

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