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 = [int(x) for x in input().split()]

d = {}

masu = [[int(x) for x in input().split()] for _ in range(H)]


for y in range(H):
    for x in range(W):
        v=masu[y][x]
        d[v-1] = (x,y)

mpDict = {}

for i in range(D):
    
    modD = i
    mpDict[modD] = {}
    index = modD
    acc = 0
    mpDict[modD][i] = 0
    index+=D
    while index<H*W:
        #print()
        #print("i",i)
        #print(index)
        prev = d[index-D]
        #print(prev)
        nxt = d[index]
        #print(nxt)
        acc += abs(prev[0]-nxt[0])+abs(prev[1]-nxt[1])
        mpDict[modD][index] = acc
        index+=D



Q = int(input())

for _ in range(Q):
    f,t = [int(x) for x in input().split()]
    modD = (f-1)%D
    mp = mpDict[modD][t-1] - mpDict[modD][f-1]
    print(mp)

Submission status: Accepted

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

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

for i in range(h):
    temp = list(map(int, input().split()))
    for j in range(w):
        p[temp[j] - 1] = [i, j]

q = int(input())
a = [[int(x) - 1 for x in input().split()] for _ in range(q)]

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

for i in range(q):
    print(s[a[i][1]] - s[a[i][0]])

Submission status: Accepted

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
p=[0]*(H*W+1)
for i in range(D+1,H*W+1):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
Q=int(input())
for _ in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Accepted

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

    p = [{} for i in range(d)]
    for i in range(h):
        for j in range(w):
            a = sq[i][j]
            p[a%d][a] = (i, j)

    sp = [[0 for j in range(len(p[i]))] for i in range(d)]
    for i in range(1, d+1):
        b, idx = i + d, 1
        i %= d

        while b <= h * w:
            x1, y1 = p[i][b][0], p[i][b][1]
            x2, y2 = p[i][b-d][0], p[i][b-d][1]
            sp[i][idx] = sp[i][idx-1] + abs(x1-x2) + abs(y1-y2)
            idx += 1
            b += d

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for h in range(H):
    L = list(map(int, input().split()))
    for w in range(W):
        position[L[w] - 1] = (h, w)

cost = [0] * (H * W)
for r in range(D):
    for j in range(r + D, H *W, D):
        A = position[j]
        B = position[j - D]
        cost[j] = cost[j - D] + abs(A[0] - B[0]) + abs(A[1] - B[1])

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

Submission status: Accepted

Solution code:
def m():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pre = [0] * ((h*w)+1)
    for i in range(h):
        for j in range(w):
            pre[a[i][j]] = (i+1, j+1)
    accum = [0] * len(pre)
    for i in range(d+1, len(pre)):
        accum[i] = accum[i - d] \
                   + abs(pre[i][0] - pre[i - d][0])\
                   + abs(pre[i][1] - pre[i - d][1])

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

m()

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
xy = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        xy[A[j]] = (i + 1, j + 1)
 
d = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
    x1, y1 = xy[i]
    x2, y2 = xy[i - D]
    d[i] = d[i - D] + abs(x1 - x2) + abs(y1 - y2)
 
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = d[R] - d[L]
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(H, W, D, A, Q, LR):
    S = [0] * (H * W + 1)
    A_ = {}
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            A_[c] = (i, j)
    
    for i in range(D+1, H*W+1):
        S[i] = S[i-D] + abs(A_[i][0]-A_[i-D][0]) + abs(A_[i][1]-A_[i-D][1])
    
    for l, r in LR:
        # print(H, W, r, l)
        print(S[r]-S[l])
    



def main():
    H, W, D = read_int_n()
    A = [read_int_n() for _ in range(H)]
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    slv(H, W, D, A, Q, LR)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  h, w, d = map(int, input().split())
  dic = {}
  for i in range(1, h + 1):
    alst = list(map(int, input().split()))
    for j in range(w):
      dic[alst[j]] = (i, j + 1)
  
  acc = []
  for i in range(d):
    lst = [0]
    a = 0
    x, y = dic[(i - 1) % d + 1]
    for j in range((i - 1) % d + 1 + d, h * w + 1, d):
      x2, y2 = dic[j]
      a += abs(x - x2) + abs(y - y2)
      x, y = x2, y2
      lst.append(a)
    acc.append(lst)
  q = int(input())
  ans = 0
  for _ in range(q):
    l, r = map(int, input().split())
    ld = l // d
    rd = r // d
    if l % d == 0:
      ld -= 1
      rd -= 1
    ans = acc[l % d][rd] - acc[l % d][ld]
    print(ans)

  
main()

Submission status: Accepted

Solution code:
H, W, D=[int(x) for x in str(input()).split()]
A=[[0 for x in range(W+1)]]
for i in range(1,H+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  A.append(b)
Q=int(input())
LR=[[0 for x in range(3)]]
for i in range(1,Q+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  LR.append(b)












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

XY=[0]
for i in range(1,D+1):

  C=[]
  x=i
  s=0
  while x<(H*W-D+1):

    s+=abs(B[x][0]-B[x+D][0])+abs(B[x][1]-B[x+D][1])
    C.append(s)
    x+=D

  C.append(s+abs(B[i][0]-B[x][0])+abs(B[i][1]-B[x][1]))
  XY.append(C)


def mo(x,y):
  if x%y==0:
    return y
  else:
    return x%y

def br(x):
  if x<=0:
    return 0
  else:
    return int(x)

ans=[]
for i in range (1,Q+1):
  if LR[i][1]<LR[i][2] and LR[i][1]==mo(LR[i][1],D):
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h)
  elif LR[i][1]<LR[i][2]:
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h-g)
  elif LR[i][1]>LR[i][2]:
    g=XY[mo(LR[i][2],D)][br((LR[i][2]+0.1)//D)-2]
    h=XY[mo(LR[i][2],D)][-1]-XY[mo(LR[i][1],D)][br((LR[i][2]+0.1)//D-2)]
    ans.append(h+g)
  else:
    ans.append(0)

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from itertools import accumulate, islice

h, w, d = map(int, input().split())
xys = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(q)]

dict_ = {v:(x, y) for y, row in enumerate(xys) for x, v in enumerate(row)}
def jump_cost(xy1, xy2):
    x1, y1 = dict_[xy1]
    x2, y2 = dict_[xy2]
    return abs(x1-x2) + abs(y1-y2)

d_ = {}
for i in range(d):
    values = range(i+1, h*w+1, d)
    startend = zip(values, islice(values, 1, None))
    costs = (jump_cost(xy1, xy2) for xy1, xy2 in startend)
    running_totals = [0] + list(accumulate(costs))
    d_.update(dict(zip(values, running_totals)))

for l, r in lrs:
    print(d_[r] - d_[l])

Submission status: Accepted

Solution code:
from itertools import accumulate

h, w, d = map(int, input().split())
xys = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(q)]

dict_ = {v:(x, y) for y, row in enumerate(xys) for x, v in enumerate(row)}
def jump_cost(xy, ab):
    x, y = dict_[xy]
    a, b = dict_[ab]
    return abs(x-a) + abs(y-b)

m = h * w
d_ = {}
for i in range(1, d+1):
    startend = zip(range(i, m+1, d), range(i+d, m+1, d))
    costs = (jump_cost(xy1, xy2) for xy1, xy2 in startend)
    d_[i % d] = [0] + list(accumulate(costs))

for l, r in lrs:
    a = r // d
    b, c = divmod(l, d)
    print(d_[c][a - (c==0)] - d_[c][b - (c==0)])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
x = [0 for _ in range(w*h)]
y = [0 for _ in range(w*h)]

for y_ in range(h):
    inp = list(map(int, input().split()))
    for x_, a in enumerate(inp):
        x[a-1] = x_
        y[a-1] = y_
    
table = [0 for _ in range(w*h)]
for d_ in range(1,d+1):
  a = d_
  b = d_ + d
  s = 0
  while b <= h*w:
    s += abs(x[a-1]-x[b-1])+abs(y[a-1]-y[b-1])
    table[b-1] = s
    b += d
    a += d
    
q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  print(table[r-1]-table[l-1])

Submission status: Accepted

Solution code:
x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i]=y
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1]=[i,j]
cost=[0*i for i in range(h*w-d)]
for i in range(h*w-d):
    cost[i]=abs(coor[i+d][0]-coor[i][0])+abs(coor[i+d][1]-coor[i][1])
ans=[0*i for i in range(h*w)]
for i in range(d,h*w):
    ans[i]=ans[i-d]+cost[i-d]
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    print(ans[r-1]-ans[l-1])

Submission status: Accepted

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

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

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

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

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

Submission status: Accepted

Solution code:
inf = float('inf')
mod = 10**9+7
from itertools import product, permutations, combinations, combinations_with_replacement
import bisect

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 = {}
for i,i2 in enumerate(A):
    for j,j2 in enumerate(i2):
        d[j2] = (i+1,j+1)

def listsub(t1,t2):
    return (abs(t1[0]-t2[0]),abs(t1[1]-t2[1]))

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

for i in range(D+1,(H*W)+1):
    dp[i] = dp[i-D] + sum(listsub(d[i-D], d[i]))

for L, R in LR:
    print(dp[R] - dp[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())
LR = [list(map(int,input().split())) for _ in range(Q)]

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}

memo = [0] * (H*W+1)
for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    memo[i] = memo[i-D] + abs(a%W - b % W) + abs(a//W - b//W)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(memo[r] - memo[l])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 13 17:57:26 2018

H 行 W 列のマス目があり、i 行目の j 列目のマスをマス (i,j) と呼びます。
このマス目には 1 から H×W までの整数が重複なく書かれており、マス (i,j) に書かれている整数は Ai,j です。
魔法少女であるあなたは、魔力 |x−i|+|y−j| を消費することでマス (i,j) に置かれた駒をマス (x,y) に瞬間移動させることができます。
あなたは、魔法少女としての能力を計るために、Q 回の実技試験を受けなければなりません。
i 回目の実技試験は、以下の手順で行われます。

•初めに、駒が整数 Li の書かれているマスに置かれている。
•駒の置かれているマスに書かれている整数を x とする。x が Ri でない限り、駒を x+D の書かれているマスに移動することを繰り返す。x=Ri となったら終了する。
•ただし、Ri−Li が D の倍数であることは保証される。

それぞれの実技試験に対し、あなたの消費する魔力の総和を求めてください。

H W D
A1,1 A1,2 … A1,W
:
AH,1 AH,2 … AH,W
Q
L1 R1
:
LQ RQ

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

出力
5


@author: Yuya
"""

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

Set = []
Dis = []

for i in range(D):
    tmp = []
    Set.append(tmp)
    tmp2 = []
    Dis.append(tmp2)

for i in range(H):
    A_i = list(map(int,input().split()))
    for j in range(W):
        tmp = A_i[j]%D
        now = [A_i[j], i, j]
        Set[tmp].append(now)

for i in range(D):
    Set[i].sort(key=lambda x:x[0])

for i in range(D):
    length = 0
    now = [Set[i][0][0], length]
    Dis[i].append(now)
    for j in range(1,len(Set[i])):
        length = length + abs(Set[i][j][1]-Set[i][j-1][1]) + abs(Set[i][j][2]-Set[i][j-1][2])
        now = [Set[i][j][0], length]
        Dis[i].append(now)
 
Q = int(input())


for i in range(Q):
    L, R = map(int,input().split())
    now_Set = L%D
    tL = (L-1)//D
    tR = (R-1)//D
    Power = Dis[now_Set][tR][1] - Dis[now_Set][tL][1]
    print(Power)

Submission status: Accepted

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

L = [(0, 0) for _ in range(H*W + 1)]
DP = [0]*(H*W + 1)

for i in range(H):
    for j, a in enumerate(inpl()):
        L[a] = (i+1, j+1)

for x in range(D, H*W+1):
    DP[x] = DP[x-D] + abs(L[x][0] - L[x-D][0]) + abs(L[x][1] - L[x-D][1])

for _ in range(int(input())):
    l, r = inpl()
    print(DP[r] - DP[l])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W+1,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [0] * H * W
for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
        A[temp[j] - 1] = (i + 1, j + 1)

Q = int(input())
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)


def consumption(point_A, point_B):
    return abs(point_A[0] - point_B[0]) + abs(point_A[1] - point_B[1])


X = []
for i in [D] + list(range(1, D)):
    power = 0
    x = [0]
    for j in range(int((H * W - i) / D)):
        power += consumption(A[i - 1 + j * D], A[i - 1 + (j + 1) * D])
        x.append(power)
        #print("{}->{}".format(A[i - 1], A[i - 1 + (j + 1) * D]))
    X.append(x)
# print(X)
for i in range(Q):
    k = L[i] % D
    if k == 0:
        l = int((L[i] - D) / D)
        r = int((R[i] - D) / D)
    else:
        l = int((L[i] - k) / D)
        r = int((R[i] - k) / D)
    #print(X[k], l, r)
    print(X[k][r] - X[k][l])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# 数字:(縦, 横)で場所を格納
F = defaultdict()
for i in range(H):
    for j in range(W):
        F[A[i][j]] = (i, j)

# コスト
C = [0] * (H*W)
for i in range(H*W):
    if i >= D:
        C[i] = C[i-D] + abs(F[i+1][0] - F[i-D+1][0]) + abs(F[i+1][1] - F[i-D+1][1])

# クエリを受けとってO(1)で計算
Q = int(input())
for q in range(Q):
    L, R = map(int, input().split())
    print(C[R-1] - C[L-1])

Submission status: Accepted

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

c = [0]*(h*w+1)
for i in range(d+1, h*w+1):
  pi, pj = l[i]
  qi, qj = l[i-d]
  c[i] = c[i-d] + abs(pi - qi) + abs(pj - qj)

q = int(input())

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

Submission status: Accepted

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

M = {}

for h in range(H):
    A = list(map(int,input().split()))
    for w in range(len(A)):
        M[A[w]] = [h,w]

anslist = []
for d in range(1,D+1):
    ans = 0
    sub_anslist = [ans]
    now = M[d]
    for i in range(d+D,(H*W)+1,D):
        nex = M[i]
        ans += abs(nex[0]-now[0])+abs(nex[1]-now[1])
        sub_anslist.append(ans)
        now = nex
    anslist.append(sub_anslist)

Q = int(input())
output = []
for q in range(Q):
    L,R = map(int,input().split())
    left = anslist[(L-1)%D][(L-1)//D]
    right = anslist[(R-1)%D][(R-1)//D]
    output.append(str(right-left))
        
print("\n".join(output))

Submission status: Accepted

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

pos = [0] * (H*W)
Z = [0] * (H*W+1)
for j in range(H):
    A = list(map(int, input().split()))
    for i in range(W):
        pos[A[i]-1] = (i, j)
for k in range(D):
    for x in range(k, H*W-D, D):
        pos1 = pos[x]
        pos2 = pos[x+D]
        Z[x+D+1] = abs(pos2[0]-pos1[0]) + abs(pos2[1]-pos1[1]) + Z[x+1]

for _ in range(int(input())):
    x, y = map(int, input().split())
    print(Z[y]-Z[x])

Submission status: Accepted

Solution code:
# PROBLEM D
h, w, d = [int(s) for s in input().split()]
Aij = [[int(s) for s in input().split()] for _ in range(h)]
q = int(input())
lrs = [[int(s) for s in input().split()] for _ in range(q)]

a2ij = {Aij[i][j]: (i, j) for i in range(h) for j in range(w)}
#print(a2ij)

cs = [0 for _ in range(h * w)]
for a in range(d + 1, h * w + 1):
    prev_sum = cs[a - d - 1]
    i0, j0 = a2ij[a - d]
    i1, j1 = a2ij[a]
    dist = abs(i0 - i1) + abs(j0 - j1)
    cs[a - 1] = prev_sum + dist
#print(cs)
    
for l, r in lrs:
    print(cs[r-1] - cs[l-1])

Submission status: Accepted

Solution code:
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for y in range(h)]
p = {}
for y in range(h):
    for x in range(w):
        p[a[y][x]] = (x, y)
dp = [0] * (h*w + 1)
for i in range(1, d+1):
    for j in range(i+d, h*w+1, d):
        cx, cy = p[j-d]
        nx, ny = p[j]
        dp[j] = abs(nx - cx) + abs(ny - cy) + dp[j-d]
q = input()
for i in range(q):
    l, r = map(int, raw_input().split())
    print(dp[r] - dp[l])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# 解説読後
import sys
sys.setrecursionlimit(100000)
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
mapper={}
for i in range(H):
    for j in range(W):
        mapper[A[i][j]]=(i,j)

Q=int(input().strip())
dist=[0]*(H*W+1)
for i in range(1,H*W+1):
    if i<=D:
        dist[i] = 0
    else:
        pos1=mapper[i]
        pos2=mapper[i-D]
        dist[i]=dist[i-D]+abs(pos1[0]-pos2[0])+abs(pos1[1]-pos2[1])
for i in range(Q):
    cst=0
    l,r=map(int,input().split())
    print(dist[r]-dist[l])

Submission status: Accepted

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

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

d = [0 for i in range(H*W+1)]
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])

Q = int(input())

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

Submission status: Accepted

Solution code:

import numpy as np


def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])

class PracticalSkillTest():

    def __init__(self):
        self.H, self.W, self.D = get_next_ints()
        self.field = []
        for _ in range(self.H):
            self.field.append(get_next_ints())
        self.Q = get_next_int()
        self.places = []
        for _ in range(self.Q):
            self.places.append(get_next_ints())
        self.mapping()
        self.dp = np.zeros(self.H * self.W+1, dtype=np.int)
        self.calc_cumulative_sum()

    def mapping(self):
        self.mapping_dic = {}
        for y in range(self.H):
            for x in range(self.W):
                self.mapping_dic[self.field[y][x]] = (x, y)


    def calc_cumulative_sum(self):
        for i in range(self.D+1, self.H*self.W+1):
            pos = self.mapping_dic[i]
            pre_pos = self.mapping_dic[i-self.D]
            self.dp[i] = self.dp[i-self.D] + abs(pos[0] - pre_pos[0]) + abs(pos[1] - pre_pos[1])
        # print(self.dp)



    def practice_solve(self):
        self.calc_cumulative_sum()
        for i in range(self.Q):
            cost = self.dp[self.places[i][1]] - self.dp[self.places[i][0]]
            print(cost)
    
def solve():
    p = PracticalSkillTest()
    p.practice_solve()

solve()

Submission status: Accepted

Solution code:
h,w,d=(int(i) for i in input().split())
num=[None for i in range(h*w)]
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        num[a[j]-1]=(i,j)
numm=[None for i in range(h*w)]
for i in range(d):
    numm[i]=0
for i in range(d,h*w):
    numm[i]=numm[i-d]+abs(num[i][0]-num[i-d][0])+abs(num[i][1]-num[i-d][1])

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

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
n2c = {i:None for i in range(1, h*w+1)}
D = [0] * (h * w + 1)
for i in range(h):
    i += 1
    for j,v in enumerate(input().split()):
        j = j + 1
        v = int(v)
        n2c[v] = (i,j)

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

def c(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

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())
a = [[0 for i in range(0,w)] for j in range(0,h)]
x = [0 for i in range(0,h*w)]
y = [0 for i in range(0,h*w)]
for i in range(0,h):
    a[i] = list(map(int,input().split()))
for j in range(0,h):
    for i in range(0,w):
        x[a[j][i]-1] = i
        y[a[j][i]-1] = j
l = []
r = []
q = int(input())
for i in range(0,q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

way = [0 for i in range(0,h*w)]
for i in range(d,h*w):
    way[i] = way[i-d] + abs(x[i] - x[i-d]) + abs(y[i] - y[i-d])
for i in range(0,q):
    print(way[r[i]-1] - way[l[i]-1])

Submission status: Accepted

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c

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

h,w,d = [int(i) for i in input().split()]
sa = list_1d(h*w+1,[])
da = list_1d(h*w+1,0)
for i in range(h):
    a = [int(k) for k in input().split()]
    for j in range(w):
        sa[a[j]] = [i,j]
q = int(input())
lr = [[int(i) for i in input().split()] for i in range(q)]

for i in range(d+1,h*w+1):
    da[i] = da[i-d] + distance_2d(sa[i],sa[i-d])

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

Submission status: Accepted

Solution code:
h,w,d = (int(i) for i in input().split())
a = [[int(i) for i in input().split()] for i in range(h)]
q = int(input())
r = [[int(i) for i in input().split()] for i in range(q)]
b,c = a[0],[]
for i in range(h*w): c.append([0,i])
for i in a[1:]: b+=i
for i in range(h*w):
	c[b[i]-1][1] = i
for i in range(d+1,h*w+1):
	x = abs(c[i-1][1]%w-c[i-d-1][1]%w)+abs((c[i-1][1]-c[i-1][1]%w)//w-(c[i-d-1][1]-c[i-d-1][1]%w)//w)
	c[i-1][0] = c[i-d-1][0]+x
for i in r:
	print(c[i[1]-1][0]-c[i[0]-1][0])

Submission status: Accepted

Solution code:
#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field_dict = {}
for h in range(H):
    field = list(map(int, input().split()))
    for w in range(W):
        field_dict[field[w]] = (h, w)

#numberからD動かした時の魔力
move_dict = {}
pre_length = 0
for now_point in range(1, H * W + 1):
    pre_point = now_point - D
    if now_point > D:
        pre_length = move_dict[now_point - D]
        now_h = field_dict[now_point][0]
        now_w = field_dict[now_point][1]
        pre_h = field_dict[pre_point][0]
        pre_w = field_dict[pre_point][1]
        move_dict[now_point] = abs(now_h - pre_h) + abs(now_w - pre_w) + pre_length
    else:
        move_dict[now_point] = 0
           
#試験
Q = int(input())
for test in range(Q):
    target = list(map(int, input().split()))
    count = move_dict[target[1]] - move_dict[target[0]]
    print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 12:24:26 2018

@author: natsukiiwano
"""
import numpy as np

_in_ = input().split(" ")
H,W,D = int(_in_[0]),int(_in_[1]),int(_in_[2])

px,py= np.zeros(90001),np.zeros(90001)
d=np.zeros(90001)
for i in range(H):
    _in_ = list(map(int,input().split(" ")))
    for j in range(W):
        px[_in_[j]]=i
        py[_in_[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])

Q = int(input())
for i in range(Q):
    _in_ = input().split(" ")
    L,R = int(_in_[0]),int(_in_[1])
    print(int(d[R]-d[L]))

Submission status: Accepted

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

a_dict = {}
for i in range(h):
  r = list(map(int, input().split()))
  for j in range(w):
    a_dict[r[j]] = [i+1, j+1]

q = int(input())

need_power = {}

for i in range(1, h*w+1):
  if i <= d:
    need_power[i] = 0
    continue

  need_power[i] = need_power[i-d] + abs(a_dict[i][0] - a_dict[i-d][0]) + abs(a_dict[i][1] - a_dict[i-d][1])

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

for t in test:                                                                                                             
  print(need_power[t[1]] - need_power[t[0]])

Submission status: Accepted

Solution code:
H,W,D = map(int, input().split())
arr = [0]*(H*W)
for i in range(H):
    for j , v in enumerate(map(int, input().split())):
        arr[v-1] = (i,j)
X = [[] for _ in range(D)]
Y = [[] for _ in range(D)]
for i , (x,y) in enumerate(arr):
    if i // D == 0:
        X[i%D].append(0)
        Y[i%D].append(0)
    else:
        px, py = arr[i - D]
        X[i%D].append(X[i%D][-1] + abs(x - px))
        Y[i%D].append(Y[i%D][-1] + abs(y - py))
Q = int(input())
for _ in range(Q):
    L, R = map(lambda x : int(x) - 1 , input().split())
    
    assert L % D  == R % D
    print(X[R%D][R//D] - X[L%D][L//D] + Y[R%D][R//D] - Y[L%D][L//D])

Submission status: Accepted

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

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

for i in range(len(A)):
        for j in range(len(A[i])):
            sA[A[i][j]] = [i, j]

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

for lr in LR:
    l, r = lr[0], lr[1]
    print(d[r] - d[l])

Submission status: Accepted

Solution code:
#abc089d

h,w,d=map(int,raw_input().split())
a=[]
for i in xrange(h):
 a.append(list(map(int,raw_input().split())))
q=int(raw_input())
p=[0 for i in xrange(h*w+1)]
for i in xrange(h):
 for j in xrange(w):
  p[a[i][j]]=(i,j)
dt=[0 for i in xrange(h*w+1)]
for i in xrange(d+1,h*w+1):
 dt[i]=dt[i-d]+abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])
l=[]
r=[]
while q:
 l,r=map(int,raw_input().split())
 print dt[r]-dt[l]
 q-=1