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: Runtime Error

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8[:,:])", cache=True)
def dfs(H, W, D, A, mp):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i][i + D] = abs(x - w) + abs(y - h)

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


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    mp = np.zeros(shape=(H * W + 1, H * W + 1), dtype=np.int64)
    dfs(H, W, D, A, mp)

    ans = [mp[l, r] for l, r in zip(L, R)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8[:,:])", cache=True)
def dfs(H, W, D, A, mp):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i][i + D] = abs(x - w) + abs(y - h)

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


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    mp = np.zeros(shape=(H * W + 1, H * W + 1), dtype=np.int64)
    dfs(H, W, D, A, mp)

    ans = [mp[l, r] for l, r in zip(L, R)]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D] - power_acc[L%D][L//D])

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(H*W):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[L%D][R//D] - power_acc[R%D][L//D])

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 6

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

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

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

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

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

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

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

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

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(a.index(i+1)-1, next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**9)


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

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

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**5)


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

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

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Submission status: Runtime Error

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

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

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Submission status: Runtime Error

Solution code:
from numba import njit 
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    h, w, d = map(int, input().split())

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

    M = 0
    for i in range(h):
        for j in g[i]:
            M = max(M, j)
    l = [0]*(M+1)
    ltup = [0]*(M+1)
    
    @njit
    def main(num):
        for i in range(h):
            for j in range(w):
                if g[i][j] == num:
                    if num <= M-d:
                        l[num] = l[num+d]+abs(ltup[num+d][0]-i)+abs(ltup[num+d][1]-j)
                    ltup[num] = (i, j)
                    num -= d
                    if num >= 0:
                        main(num)
                    else:
                        return False
    for i in range(d):
        main(M-i)
    
    q=int(input())
    for i in range(q):
        lc,rc=map(int,input().split())
        print(l[lc]-l[rc])



resolve()

Submission status: Runtime Error

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

px = {i:0 for i in range(H*W)}
py = {i:0 for i in range(H*W)}

for i in range(H):
  for j in range(W):
    A = area[i][j]
    px[A] = i
    py[A] = j
    
d = {i:0 for i in range(H*W)}

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

Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]
for lr in LR:
  print(d[lr[1]] - d[lr[0]])

Submission status: Runtime Error

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

potions = dict()

for px in range(H):
  for py in range(W):
    potions[area[px][py]] = [px,py]
    
d = {i:0 for i in range(H*W)}

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

Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]
for lr in LR:
  print(d[lr[1]] - d[lr[0]])

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc089/tasks/abc089_d

def calc(x):
    if x<D+1:
        mv[x]=0
        return 0
    else:
        p = d[x][0]
        q = d[x][1]
        r = d[x-D][0]
        s = d[x-D][1]
        tmp = abs(p-r)+abs(q-s)
        ret= tmp+calc(x-D)
        mv[x]=ret
        return ret
    
H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())

d=dict()
z=0
for a in A:
    for b in a:
        p = z//W
        q = z%W
        d[b]=(p,q)
        z+=1
        
mv=[0]*(H*W+1)
for i in range(D):
    calc(H*W-i)
    #print(H*W-i,calc(H*W-i))    
#print(mv)

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

Submission status: Runtime Error

Solution code:
#float型を許すな
#numpyはpythonで
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, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h+1)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]]=[i,j]
#print(lis)
cost=[[0]*(h*w) for i in range(d)]
for i in range(d):
    cost[i][i]=0
    for j in range(1,h*w):
        if i+d*j<h*w:
            cost[i][i+d*j]=cost[i][i+d*j-d]+abs(lis[i+d*j][0]-lis[i+d*(j-1)][0])+abs(lis[i+d*j][1]-lis[i+d*(j-1)][1])
            
        
#print(cost)
q=I()
for i in range(q):
    ans=0
    l,r=MI()
    k=l%d
    print(cost[k][r]-cost[k][l])

Submission status: Runtime Error

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

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

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

for i in range(w):
    for j in range(h):
        s = ab[i][j]
        dp[s] =[i,j]
        
dpp= [0]*(h*w+1)

for k in range(d+1,h*w+1):
#    print(k)
    dpp[k] = dpp[k-d] + abs(dp[k][0]-dp[k-d][0]) +abs(dp[k][1]-dp[k-d][1])
    
q = int(input())

for x in range(q):
    a,b = map(int, input().split())
    print(dpp[b]-dpp[a])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)

X=[]
for d in range(D):
  p=P[(d+D)%(D+1)::D]
  n=len(p)
  _=[sub(p[(i+1)%n],p[i]) for i in range(n)]
  X.append(_)
Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  if l>r:
    r+=N
  g=l%D
  ans=0
  for i in range(l,r,D):
    ans+=X[g][(i%N)//D]
  print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  h, w, d = map(int, input().split())
  mat_a = numpy.array([list(map(int, input().split())) for _ in range(h)])
  q = int(input())
  x_to_pos = dict()
  
  for i in range(h):
    for j in range(w):
      x_to_pos[mat_a[i, j]] = (i, j)
      
  def calc_score(p1, p2):
    return sum([abs(x-y) for x, y in zip(p1, p2)])
  
  visited = numpy.zeros((h, w))
  costs = defaultdict(dict)
  for x in range(1, d+1):
    c = x
    cost = 0
    costs[c%d][c%d] = 0
    while True:
      cp = x_to_pos[c]
      c += d
      if c > (h*w):
        break
      np = x_to_pos[c]
      cost += calc_score(cp, np)
      costs[c%d][c] = cost
      
  for _ in range(q):
    cost = 0
    l, r = map(int, input().split())
    print(abs(costs[l%d][l] - costs[l%d][r]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  h, w, d = map(int, input().split())
  mat_a = numpy.array([list(map(int, input().split())) for _ in range(h)])
  q = int(input())
  x_to_pos = dict()
  
  for i in range(h):
    for j in range(w):
      x_to_pos[mat_a[i, j]] = (i, j)
      
  def calc_score(p1, p2):
    return sum([abs(x-y) for x, y in zip(p1, p2)])
  
  visited = numpy.zeros((h, w))
  costs = defaultdict(dict)
  for x in numpy.sort(mat_a.reshape(-1)):
    c = x
    cost = 0
    costs[c%d][c%d] = 0
    if x > d:
      continue
    while True:
      cp = x_to_pos[c]
      c += d
      if c not in x_to_pos.keys():
        break
      np = x_to_pos[c]
      cost += calc_score(cp, np)
      costs[c%d][c] = cost
      
  for _ in range(q):
    cost = 0
    l, r = map(int, input().split())
    if l == r:
      print(0)
    else:
#       print(l, r, l%d, costs)
      print(abs(costs[l%d][l] - costs[l%d][r]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# Dかそれぞれのqueryで固定なのでこの問題は解ける
H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()
# piece[0]からpiece[1]まで
# 4 → 6　→ 8
piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]

# 飛ばし累積和
x_plus = []
y_plus = []
for i in range(D):
    list_x = [0]
    list_y = [0]
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
        list_x.append(list_x[-1] + opt_x)
        list_y.append(list_y[-1] + opt_y)
    list_x.pop(0)
    list_y.pop(0)
    x_plus.append(list_x)
    y_plus.append(list_y)

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    mul = (start - 1) % D
    x_point = x_plus[mul][(goal - mul) // D] - x_plus[mul][(start - mul) // D]
    y_point = y_plus[mul][(goal - mul) // D] - y_plus[mul][(start - mul) // D]
    return x_point + y_point
    
for i in range(Q):
    print(past_exam(piece[i]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from collections import defaultdict

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

dic = defaultdict(list)

for h in range(W):
    for w in range(W):
        dic[A[h][w]] = [h, w]

def calc(l, r):
    return abs(dic[l][0] - dic[r][0]) + abs(dic[l][1] - dic[r][1])

lst = [0] * (H * W + 1)
for d in range(1, D + 1):
    tmp = d
    while tmp + D <= (H * W):
        lst[tmp + D] = lst[tmp] + calc(tmp, tmp + D)
        tmp += D

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

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
MAX = H*W
M = MAX//D+1
dic = {}

for i in range(H):
  temp = list(map(int,input().split()))
  for j in range(W):
    now = temp[j]
    dic[now] = (i,j)
#print(dic)
L = [[0] for _ in range(M)]
for i in range(D): #MODで0からD-1をひたすら見ていく。
  if i == 0:
    now = D
  else:
    now = i
  while now+D <= MAX:
    tsugi = now+D
    np = dic[now] #今の場所
    tp = dic[tsugi]
    dis = abs(np[0]-tp[0])+abs(np[1]-tp[1])
    L[i].append(L[i][-1]+dis)
    now = tsugi
#print(L,L[0])
Q = int(input())
for i in range(Q):
  left,right = map(int,input().split())
  MOD = left%D
  #print(L[MOD])
  start = (left-1)//D
  end = (right-1)//D
  ans = L[MOD][end]-L[MOD][start]
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from collections import defaultdict

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

dic = defaultdict(list)

for h in range(W):
    for w in range(W):
        dic[A[h][w]] = [h, w]

def calc(l, r):
    return abs(dic[l][0] - dic[r][0]) + abs(dic[l][1] - dic[r][1])

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = 0
    while L != R:
        ans += calc(L, L + D)
        L += D
    print (ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

A = [list(map(int, input().split())) for _ in range(H)]
aToHW = {}
for h, row in enumerate(A):
    for w, a in enumerate(row):
        aToHW[a] = (h, w)

Q = int(input())

@lru_cache(maxsize=None)
def search(now):
    if not now + D in aToHW:
        return 0

    l, r = aToHW[now], aToHW[now + D]
    return abs(l[0] - r[0]) + abs(l[1] - r[1]) + search(now + D)

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

    ans.append(search(l) - search(r))

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

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]
for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]
for i in range(h * w-d):
    num[i%d][i//d+1] = num[i%d][i//d]+abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])
q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(num[now%d-1][(goal-now%d)//d-1]-num[now%d-1][(now-now%d)//d-1])
    else:
        print(num[now%d-1][(goal-now%d)//d]-num[now%d-1][(now-now%d)//d])

Submission status: Runtime Error

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

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

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

m = [0]*(H*W)
for i in range(1,H*W):
    if i+D <= H*W:
        m[i] = abs(d[i][0] - d[i+D][0]) + abs(d[i][1] - d[i+D][1])
s = [[] for _ in range(D+1)]
for i in range(1,D+1):
    cost = 0
    for j in range(i,H*W-D+1,D):
        cost += abs(d[j][0] - d[j+D][0]) + abs(d[j][1] - d[j+D][1])
        s[i].append(cost)

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

Submission status: Runtime Error

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

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

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(H * W // D + 1) - 1):
        t[i][j + 1] += t[i][j]

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

Submission status: Runtime Error

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

d = {}
for y in range(H):
    Ay = A[y]
    for x in range(W):
        d[Ay[x]] = (y, x)

t = [[0] * ((H * W + D - 1) // D) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(ti) - 1):
        ti[j + 1] += ti[j]

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]
    P = defaultdict(list)
    for d in range(1, D + 1):
        a = d
        while a <= H * W - D:
            p = abs(M[a][0] - M[a + D][0]) + abs(M[a][1] - M[a + D][1])
            if P[d]:
                P[d].append(P[d][-1] + p)
            else:
                P[d] = [0, p]
            a += D
    # print(P)
    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = L % D
        l = L // D
        r = R // D
        if d == 0:
            d = D
            if len(P[d]) > 0:
                print(P[d][r - 1] - P[d][l - 1])
            else:
                print(0)
        else:
            print(P[d][r] - P[d][l])


if __name__ == "__main__":
    main()