Problem:


Score : 400 points

Problem Statement

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

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

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

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

The i-th test will be conducted as follows:

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

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

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

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

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

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

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

1 \leq Q \leq 10^5

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

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

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

Output

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

Output should be in the order the tests are conducted.

Sample Input 1

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

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

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

Sample Input 2

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

Sample Output 2

0
0

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

Sample Input 3

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

Sample Output 3

0
5
0



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


Sample output:
5

Submission status: Accepted

Solution code:
import math

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

coordinate = [[0, 0] for _ in range(H*W+1)]  # coordinate(n) = [nのi座標, nのj座標]
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        coordinate[A[j]] = [i, j]

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


def dist(coord1, coord2):
    return int(math.fabs(coord1[0] - coord2[0]) + math.fabs(coord1[1] - coord2[1]))


imos = []
imos.append([])
for d in range(1, D+1):
    lst = [0]
    while d + D <= H * W:
        distance = dist(coordinate[d], coordinate[d + D])
        lst.append(distance)
        d += D
    imos.append(lst)

for d in range(1, D+1):
    for i in range(len(imos[d])-1):
        imos[d][i+1] += imos[d][i]

for q in range(Q):
    d = L[q] % D
    if d == 0:
        print(imos[D][int(R[q] / D) - 1] - imos[D][int(L[q] / D) - 1])
    else:
        print(imos[d][int(R[q] / D)] - imos[d][int(L[q] / D)])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = []
C = [0 for _ in range(H * W + 1)]
for h in range(H):
    A.append(list(map(lambda x: int(x) - 1, input().split())))
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
h = [0 for _ in range(H * W)]
for i in range(D):
    s = 0
    for j in range(i, H * W, D):
        if j != i:
            n = (C[j][0], C[j][1])
            p = (C[j - D][0], C[j - D][1])
            s += abs(n[0] - p[0]) + abs(n[1] - p[1])
        h[j] = s
Q = int(input())
for _ in range(Q):
    l, r = map(lambda x: int(x) - 1, input().split())
    print(h[r] - h[l])

Submission status: Accepted

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

pos = [[None for i in range(D)] for j in range(H*W//D + 1)]
for y in range(H):
    for x in range(W):
        a = src[y][x]
        b,c = a//D, a%D
        pos[b][c] = (x,y)

cums = [[0] for i in range(D)]
for i in range(D):
    for j in range(H*W//D):
        if pos[j][i] is None or pos[j+1][i] is None:
            cums[i].append(cums[i][-1])
        else:
            x1,y1 = pos[j][i]
            x2,y2 = pos[j+1][i]
            dist = abs(x1-x2) + abs(y1-y2)
            cums[i].append(cums[i][-1] + dist)
            
for l,r in qs:
    d = l%D
    print(cums[d][r//D] - cums[d][l//D])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
A = [[int(x) for x in input().split()] for x in range(h)]
Q = int(input())
LR = [[int(x) for x in input().split()] for x in range(Q)]
num = [[[0,0] for x in range(h*w//d+1)] for y in range(d)]
for i in range(h):
    for j in range(w):
        n = A[i][j]
        num[n%d][n//d] = [i,j]
numsum = [[0 for x in range(h*w//d+1)] for y in range(d)]

for y in range(d):
    for x in range(1,h*w//d+1):
        a,b = num[y][x-1]
        i,j = num[y][x]
        numsum[y][x] = numsum[y][x-1]+abs(a-i)+abs(b-j)
for l,r in LR:
    print(numsum[r%d][r//d]-numsum[l%d][l//d])

Submission status: Accepted

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

mp = {}
now = 0

for a in range(h):
  z = map(int,raw_input().split(" "))
  for zz in z:
    mp[zz] = now
    now += 1

data = [-1] * (h*w + 1)
data2 = [-1] * (h*w + 1)

for a in range(d+1,h*w+1):
  l = mp[a-d]
  r = mp[a]
  x = abs((r/w) - (l/w))
  y = abs((r%w) - (l%w))
  data[a] = x+y
  if a - d <= 0:
    continue
  data2[a] = data2[a-d] + data[a]

q = int(raw_input())

for a in range(q):
  l,r = map(int,raw_input().split(" "))
  print data2[r] - data2[l]

Submission status: Accepted

Solution code:
H,W,D = map(int, input().split())
map_ = []
for i in range(H):
    map_.append(list(map(int, input().split())))
    
#for i in range(H):
#    print(map_[i])

n_to_pos = [[0,0]] * (H * W + 1)
for i in range(H):
    for j in range(W):
        n_to_pos[map_[i][j]] = [i,j]

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

Q = int(input())
for i in range(Q):
    B,E = map(int, input().split())
    print(reach_cost[E]-reach_cost[B])

Submission status: Accepted

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

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

# print(cost)

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

Submission status: Accepted

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

import itertools


class CumulativeSum(object):
    """Constructs the cumulative sum of the elements in the given sequence.

    :param sequence: The sequence to be processed.
    :type sequence: sequence
    """

    def __init__(self, sequence):
        self.cumulative_sum = [0]
        self.cumulative_sum.extend(itertools.accumulate(sequence))

    def partial_sum(self, first, last):
        """Computes the partial sum of the sequence.

        :param first: The index representing the first element of the
                      subsequence.
        :type first: int
        :param last: The index representing the last element of the
                     subsequence.
        :return: The partial sum.
        """
        return self.cumulative_sum[last + 1] - self.cumulative_sum[first]


def prepare(h, w, d, board):
    val2pos = [None for _ in range(h * w + 1)]
    for r, c in itertools.product(range(h), range(w)):
        val2pos[board[r][c]] = (r, c)
    max_e = h * w // d
    cumsums = []
    for m in range(d):
        max_e = (h * w - m) // d
        costs = []
        for e in range(max_e + 1):
            if e == 0:
                costs.append(0)
            else:
                x0 = (e - 1) * d + m
                if x0 != 0:
                    r0, c0 = val2pos[x0]
                    x1 = e * d + m
                    r1, c1 = val2pos[x1]
                    cost = abs(r1 - r0) + abs(c1 - c0)
                else:
                    cost = 0
                costs.append(cost)
        cumsums.append(CumulativeSum(costs))
    return cumsums


def main():
    h, w, d = (int(x) for x in input().split())
    board = [[int(b) for b in input().split()] for _ in range(h)]
    cumsums = prepare(h, w, d, board)
    q = int(input())
    for _ in range(q):
        l, r = (int(x) for x in input().split())
        dl, ml = divmod(l, d)
        dr, mr = divmod(r, d)
        res = cumsums[ml].partial_sum(dl + 1, dr)
        # print(cumsums[ml].cumulative_sum)
        # print(dl + 1, dr)
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
m = [None] * (H*W+1) # 数値の場所
s = [0] * (H*W+1) # その数値までD刻みで移動する累積コスト
for y in range(H):
  A = list(map(int, input().split()))
  for x, a in enumerate(A):
    m[a] = (x, y)

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

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

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
P = [None]*(H*W+1)
for i in range(H):
    for j in range(W):
        P[A[i][j]] = (i, j)
C = [0]*(H*W+1)
for i in range(D+1, H*W+1):
    pi, pj = P[i]; qi, qj = P[i-D]
    C[i] = C[i-D] + abs(pi - qi) + abs(pj - qj)

ans = []
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans.append(C[R] - C[L])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

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

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

d_map = [0] * (h * w)
for l in range(h * w - d - 1, -1, -1):
    i, j = c_map[l]
    i2, j2 = c_map[l + d]
    d_map[l] = d_map[l + d] + abs(i - i2) + abs(j - j2)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    buf.append(d_map[l - 1] - d_map[r - 1])

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

Submission status: Accepted

Solution code:
H,W,D = map(int,raw_input().split())
P = [None]*(H*W+1)
for y in range(H):
  A = map(int,raw_input().split())
  for x in range(W):
    P[A[x]] = (y,x)
B = [0]*(H*W+1)
for i in range(D+1,H*W+1):
  B[i] = B[i-D] + abs(P[i][0]-P[i-D][0])+abs(P[i][1]-P[i-D][1])
Q = input()
ans = 0
for _ in range(Q):
  L,R = map(int,raw_input().split())
  print B[R]-B[L]

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,d = LI()
    a = [LI() for _ in range(h)]
    q = I()
    lr = [LI() for _ in range(q)]
    t = {}
    for i in range(h):
        for j in range(w):
            t[a[i][j]] = (i,j)


    k = [0] * (h*w+1)
    for i in range(d+1,h*w+1):
        k[i] = k[i-d] + abs(t[i][0] - t[i-d][0]) + abs(t[i][1] - t[i-d][1])
    rr = []
    for l,r in lr:
        rr.append(k[r]-k[l])

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)
INF = 10**10

(H, W, D) = reads()
L = W * H

inv = [None] * L


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

psum = [0] * L

def dist(p, q):
    (x, y) = p
    (z, w) = q
    return abs(y-w) + abs(z-x)

for i in range(D, L):
    psum[i] = psum[i-D] + dist(inv[i], inv[i-D])

# print(psum, file=stderr)

Q = read()

for i in range(Q):
    (L, R) = reads()
    print(psum[R-1] - psum[L-1])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w, d = na()
a = []
for i in range(h):
    a.append(na())

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

xs = []
for i in range(d):
    row = [0]
    for j in range(i+d, h*w, d):
        row.append(row[-1] +
                   abs(wh[j][0]-wh[j-d][0]) +
                   abs(wh[j][1]-wh[j-d][1]))
    xs.append(row)

q = ni()
for z in range(q):
    l, r = na()
    l -= 1; r -= 1
    print(xs[l%d][r//d]-xs[l%d][l//d])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w,d=map(int,input().split())
inds={}
for i in range(h):
    for d,j in enumerate(input().split()):
        inds[int(j)-1]=(i,d)
nows=[[0]for c in range(d)]
for k in range(d,h*w):
    a,b=inds[k]
    x,y=inds[k-d]
    k%=d
    nows[k].append(nows[k][-1]+abs(a-x)+abs(b-y))
q=input()
for i in inputs():
    l,r=map(int,i.split())
    l-=1;r-=1
    l,b=divmod(l,d)
    r,b=divmod(r,d)
    print(nows[b][r]-nows[b][l])

Submission status: Runtime Error

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

from collections import defaultdict
G = defaultdict(list)
for i in range(h):
    l = list(map(int, input().split()))
    for n, item in enumerate(l):
        G[item] = [n,i]




# magic is just distance by 1

# if d is 4,
# 1,5,9 or 2,6,10.. make surplus to categorize
# query comes 10^5, so O(1) or O(logN) is limit -> cumulativesum

dp = [0 for i in range(h*w)]
for i in range((h*w)%d+1): # 1,2,...d
    current_place = i+1
    while current_place + d < h*w:
        x,y = G[current_place]
        next_place = current_place + d
        x1,y1 = G[next_place]
        magic = abs(x-x1) + abs(y-y1)
        dp[next_place] = magic + dp[current_place]
        current_place = next_place

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

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
A = np.array(A)
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
for _ in range(Q):
    ans = 0
    l, r = na()
    t = (r - l) // D
    for j in range(t):
        px, py = d[l + j * D]
        nx, ny = d[l + (j + 1) * D]
        #print(px, py, nx, ny)
        ans += abs(px - nx) + abs(py - ny)
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)

b_dict={}
for i in range(1,h*w):
  if i-d<=0:
    b_dict[i]=0
  else:
    oy,ox=a_dict[i-d]
    ny,nx=a_dict[i]
    b_dict[i]=b_dict[i-d]+abs(ny-oy)+abs(nx-ox)

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

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

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

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


cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        u = np.where(arr == l)
        v = np.where(arr == l + d)
        score += abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0])
        result[i].append(score)
        l += d


result = solve(h, w, d, arr)


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])

Submission status: Runtime Error

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import accumulate
import numpy as np

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

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

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

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


result = defaultdict(list)

for i in range(d):
    l = i
    while l + d <= h * w:
        if l == 0:
            result[i].append(0)
            l += d
            continue
        u = np.where(arr == l)
        v = np.where(arr == l + d)
        result[i].append(abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0]))
        l += d

for i in range(d):
    result[i] = list(accumulate(result[i]))

ans = []
for l, r in lr:
    arr = result[l % d]
    ans.append(arr[r // d - 1] - arr[l // d - 1])

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[0,0]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())
  u=H*W
  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=l*D
    print(ans)
  return
main()

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())
  u=H*W
  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=l*D
    print(ans)
  return
main()

Submission status: Runtime Error

Solution code:
h,w,D = map(int,input().split())
a=[]

for _ in range(h):
    b=list(map(int,input().split()))
    a.append(b)

d={}
for i in range(h):
    c=a[i]
    for j in range(w):
        d[c[j]]=(i+1,j+1)


R_min=h*w
R_max=1
query=[]
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    query.append([l,r])
    R_min = min(l,R_min)
    R_max = max(r,R_max)


cum=[0]*(h*w)
prev=0
cum[R_min]=0
for k in range(R_min,R_max-D+1):
    prev = cum[k-1]
    cost = abs(d[k+D][0]-d[k][0]) + abs(d[k+D][1]-d[k][1])
    cum[k+D-1]=cost+prev



for j in range(q):
    l,r=query[j][0],query[j][1]

    score = cum[r-1]-cum[l-1]

    if l==r:
        score=0
    

    print(score)

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      a[j]
      d[a[j]-1]=[i,j]

  Q=int(pin())

  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L 
    for l in range(1,t+1):
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=l*D
    print(ans)
  return 
main()
#動いてくれ!!

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, i8

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

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

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

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


@njit
def solve(arr, lr, d):
    ans = []
    for l, r in lr:
        score = 0
        while l != r:
            tmp = l + d
            u = np.where(arr == l)
            v = np.where(arr == tmp)
            score += (abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0]))
            l += d
        ans.append(score)
    return ans


print(*solve(arr, lr, d), sep="\n")

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for h in range(H):
    grid[h] = list(map(int, input().split()))
number_yx = [[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x in range(W):
        number_yx[grid[y][x]] = [y,x]
fromto_cost = [[0]*(1+H*W) for _ in range(1+H*W)]
for mod_group in range(D):
    # 剰余ごとにスタートを決定
    previous = mod_group+1
    start = previous
    fromto_cost[start][start] = 0
    previous_y, previous_x = number_yx[previous]
    cost = 0
    while previous+D <= (H*W):
        Next = previous+D 
        Next_y, Next_x = number_yx[Next]
        cost += abs(Next_y-previous_y) + abs(Next_x-previous_x)
        fromto_cost[start][Next] = cost

        previous = Next
        previous_y,previous_x = Next_y,Next_x

Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
    start, goal = map(int,input().split())
    mod = start % D
    base = mod
    if base == 0:
        base = D 
    base_to_goal = fromto_cost[base][goal]
    base_to_start = fromto_cost[base][start]
    ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
    print(ans)

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for h in range(H):
    grid[h] = list(map(int, input().split()))
number_yx = {}
for y in range(H):
    for x in range(W):
        number_yx[grid[y][x]] = [y,x]
fromto_cost = [[0]*(1+H*W) for _ in range(1+H*W)]
for mod_group in range(D):
    # 剰余ごとにスタートを決定
    previous = mod_group
    if previous == 0:
        previous = D
    start = previous
    fromto_cost[previous][previous] = 0
    previous_y, previous_x = number_yx[previous]
    cost = 0
    while previous+D <= (H*W):
        Next = previous+D 
        Next_y, Next_x = number_yx[Next]
        cost += abs(Next_y-previous_y) + abs(Next_x-previous_x)
        fromto_cost[start][Next] = cost

        previous = Next
        previous_y,previous_x = Next_y,Next_x

Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
    start, goal = map(int,input().split())
    mod = start % D
    base = mod
    if base == 0:
        base = D 
    base_to_goal = fromto_cost[base][goal]
    base_to_start = fromto_cost[base][start]
    ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
    print(ans)

Submission status: Runtime Error

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

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

cost=[0]*(h*w-d)

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


ans=0

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

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

memo = [[-1]*(W*H+1) for _ in range(W*H+1)]

for i in range(Q):
    L = LR[i][0]
    R = LR[i][1]
    useMP = 0
    if memo[L][R] == -1:
        point = range(L,R+1,D)
        for p in range(1,len(point)):
            x0,y0 = dict_map[point[p-1]]
            x1,y1 = dict_map[point[p]]
            useMP += abs(x0-x1)+abs(y0-y1)
            memo[(point[p-1])][point[p]]=abs(x0-x1)+abs(y0-y1)
        memo[L][R]=useMP 
          
    else:
        useMP = memo[L][R]
    print(useMP)

Submission status: Runtime Error

Solution code:
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)

Submission status: Runtime Error

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

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

B = sorted(B)

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

for i in range(H*W // D +2):
  if i > H*W:break
  for j in range(D):
    if j + i*D > H*W-1:break
    idx = j + i*D
    if i > 0:diff=abs(B[idx][1][0])+abs(B[idx][1][1])
    else:diff=abs(B[idx-D][1][0])+abs(B[idx-D][1][1])
    cum[j].append(cum[j][-1]+diff)
    
for q in range(Q):
  l, r = lr[q]
  if l==r:
    print(0)
    continue
  q1,j=divmod(r,D)
  q2 = l // D
  print(cum[j][q1+1]-cum[j][q2+1])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10000)
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

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

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

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

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

# 1 -> 1+D ->
# 2 -> 2+D ->
# 3 -> 3+D -> みたいなものを事前に計算

# 辞書で管理する
# d[A[i][j]] = [i,j] みたいな感じ
d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)

    p.append(q)


for l, r in LR:
    i = l % D - 1
    s = (l + i) // D
    e = (r + i) // D
    print(p[i][e] - p[i][s])

Submission status: Runtime Error

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

# 1 -> 1+D ->
# 2 -> 2+D ->
# 3 -> 3+D -> みたいなものを事前に計算

P = []
for k in range(1, D + 1):
    q = []
    for d in range(k, H * W + 1, D):
        for i in range(H):
            try:
                n = A[i].index(d)
                q.append([i, n])
                break
            except:
                continue
    P.append(q)

d = []

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

for l, r in LR:
    i = l % D - 1
    s = (l + i) // D
    e = (r + i) // D
    print(d[i][e] - d[i][s])

Submission status: Runtime Error

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

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

d=[0]*(H*W)
for i in range(D, H*W):
  px,py = c[i-D]
  x, y = c[i]
  d[i]=d[i-D] + abs(x-px) + abs(y-py)
for l, r in LR:
  print(d[r]-d[l])