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:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
flag = 1
if h==1 and w==1:
    flag = 0

for hh in range(h):
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    if flag == 0:
        break
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
    if ruiseki[i][h*w//d] == 0:
        ruiseki[i].pop()
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
    if ruiseki2[i][h*w//d-1] == 0:
        ruiseki2[i].pop()
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
    if ruiseki3[i][h*w//d-1] == 0:
        ruiseki3[i].pop()
# print(ruiseki3)

for i in range(n):
    if flag == 0:
        print(0)
        continue
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])

Submission status: Runtime Error

Solution code:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
flag = 1
if h==1 and w==1:
    flag = 0

for hh in range(h):
    if flag == 0:
        break
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    if flag == 0:
        break
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
    if ruiseki[i][h*w//d] == 0:
        ruiseki[i].pop()
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
    if ruiseki2[i][h*w//d-1] == 0:
        ruiseki2[i].pop()
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
    if ruiseki3[i][h*w//d-1] == 0:
        ruiseki3[i].pop()
# print(ruiseki3)

for i in range(n):
    if flag == 0:
        print(0)
        continue
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])

Submission status: Runtime Error

Solution code:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
for hh in range(h):
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
    if ruiseki[i][h*w//d] == 0:
        ruiseki[i].pop()
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
    if ruiseki2[i][h*w//d-1] == 0:
        ruiseki2[i].pop()
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
    if ruiseki3[i][h*w//d-1] == 0:
        ruiseki3[i].pop()
# print(ruiseki3)

for i in range(n):
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])

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()))
    
index=[[-1,-1] for _ in range(H*W+1)]

for i in range(H):
    for j in range(W):
        index[A[i][j]]=[i,j]
   
        
    
S=[[0]*(H*W//D) for _ in range(D+1)]
for start in range(1,D+1):
    for j in range(H*W//D-1):
        prev=start+j*D
        nxt=prev+D
        diff=abs(index[nxt][0] - index[prev][0]) + abs(index[nxt][1] - index[prev][1])
        S[start][j+1]=S[start][j]+diff
        
Q=int(input())
        
for i in range(Q):
    L,R=map(int,input().split())
    start=L%D
    if start==0:
        start=D
    print(S[start][(R-start)//D] - S[start][(L-start)//D])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
mass = np.array((0, 0) for _ in range(num + 1))
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        mass[a] = [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
mass = np.array([[0] for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        mass[a] = [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
h, w, d = map(int, read().split())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, readline().split())):
        mass[a] = [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(read())
for _ in range(q):
    l, r = map(int, read().split())
    print(mp[r]-mp[l])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin
h, w, d = map(int, input().split())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(list(map(int, input().split()))):
        mass[a] += [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])

Submission status: Runtime Error

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp.append(mp_i.cumsum())
for _ in range(q):
    l, r = map(int, input().split())
    n = (r - l) // d
    u = l % d
    index = (l - (d - u)) // 2
    if n == 0:
        print(0)
    elif index == 0:
        print(mp[u-1][index+n-1])
    else:
        print(mp[u-1][index+n-1]-mp[u-1][index-1])

Submission status: Runtime Error

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp.append(mp_i.cumsum())
for _ in range(q):
    l, r = map(int, input().split())
    n = (r - l) // d
    u = l % d
    index = (l - (d - u)) // 2
    if index == 0:
        print(mp[u-1][index+n-1])
    else:
        print(mp[u-1][index+n-1]-mp[u-1][index-1])

Submission status: Runtime Error

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp.append(mp_i.cumsum())
for _ in range(q):
    l, r = map(int, input().split())
    n = (r - l) // d
    u = l % d
    index = (l - (d - u)) // 2
    if index == 0:
        print(mp[-(u+1)][index+n-1])
    else:
        print(mp[-(u+1)][index+n-1]-mp[-(u+1)][index-1])

Submission status: Runtime Error

Solution code:
import numpy as np
h, w, d = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(h)])
q = int(input())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = []
for i in range(h):
    for j in range(w):
        a_ij = a[i][j]
        mass[a_ij] = [i, j]
for i in range(d):
    mass_sort = mass[1+i::d]
    mp_i = np.sum(abs(mass_sort[:-1] - mass_sort[1:]), axis=1)
    mp_i = np.append(np.zeros(1, dtype=int), mp_i.cumsum())
    mp.append(mp_i)
for _ in range(q):
    l, r = map(int, input().split())
    n = (r - l) // d
    u = l % d
    index = (l - (d - u)) // 2
    print(mp[-(u+1)][index+n]-mp[-(u+1)][index])

Submission status: Runtime Error

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

INF = float('inf')
h = 0--(H*W)//D
pos = [[INF]*h for _ in range(D)]
for i,row in enumerate(A):
    for j,a in enumerate(row):
        d,m = divmod(a,D)
        pos[m][d] = (i,j)

dists = [[0] for _ in range(D)]
for i,p in enumerate(pos):
    for p1,p2 in zip(p,p[1:]):
        if p1==INF or p2==INF: continue
        a1,b1 = p1
        a2,b2 = p2
        dist = abs(a1-a2) + abs(b1-b2)
        dists[i].append(dists[i][-1] + dist)

ans = []
for l,r in LR:
    a,i = divmod(l,D)
    b,j = divmod(r,D)
    if i==0:
        a-=1; b-=1
    ans.append(dists[i][b] - dists[i][a])
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
h,w,d =map(int,input().split())
a=[]
mp=[0 for i in range(h*w)]
for i in range(h):
  b =[int(x) for x in input().split()]
  a.append(b)
  for j in range(w):
    mp[b[j]]=[i,j]
for i in range(n):
  if(i+d>=n):
    break
  mp[i+d] += mp[i]
q=(int)(input())
for _ in range(q):
  l,r = map(int,input().split())
  ans = mp[r]-mp[max(0,l-d)]
  print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
#途中

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

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

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

#print(loc)

for i in range(H):
    for j in range(W):
        loc[A[i][j]-1][0]=i
        loc[A[i][j]-1][1]=j
        #print(loc)
print(loc)

cost=[[0]*((H*W)//D) for i in range(D)]

for i in range((H*W)%D):
    cost[i].append(0)

for i in range(D):
    pass
    count=1
    temp=0
    while temp<(H*W):
        temp=i+D*count
        cost[temp%D][temp//D]=abs(loc[temp][0]-loc[temp-D][0])+abs(loc[temp][1]-loc[temp-D][1])+cost[temp%D][temp//D-1]
        count+=1

print(cost)

Submission status: Runtime Error

Solution code:

#import numpy as np


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



mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



H,W,D=acinput()
#Ad={}
Ad=[0]*(H*W+1)
for i in range(H):
    ar=acinput()
    for j,sar in enumerate(ar):
        #Ad[sar]=np.array((i,j))
        Ad[sar] = (i, j)

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

for x in range(1, H*W+1):
    dp[x][x]=0

for x in range(1,H*W+1):
    y=x+D
    while True:
        if y > H*W:
            break
        #print(x,y)
        #tmp = Ad[y]-Ad[y-D]
        #S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        #tmp = Ad[y]-Ad[y-D]
        S = abs(Ad[y][0]-Ad[y-D][0])+abs(Ad[y][1]-Ad[y-D][1])

        dp[x][y]=dp[x][y-D]+S
        y+=D
        

#print(np.array(dp))

Q=int(input())
for i in range(Q):
    l,r=acinput()
    print(dp[l][r])


#print(Ad)
#print(np.array(dp))

Submission status: Runtime Error

Solution code:

import numpy as np


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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

H,W,D=acinput()
#Ad={}
Ad=[0]*(H*W+1)
for i in range(H):
    ar=acinput()
    for j,sar in enumerate(ar):
        Ad[sar]=np.array((i,j))

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

for x in range(1, H*W+1):
    dp[x][x]=0

for x in range(1,H*W+1):
    y=x+D
    while True:
        if y > H*W:
            break
        #print(x,y)
        tmp = Ad[y]-Ad[y-D]
        S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        dp[x][y]=dp[x][y-D]+S
        y+=D
        

#print(np.array(dp))

Q=int(input())
for i in range(Q):
    l,r=acinput()
    print(dp[l][r])


#print(Ad)
#print(np.array(dp))

Submission status: Runtime Error

Solution code:

import numpy as np


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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

H,W,D=acinput()
#Ad={}
Ad=[0]*(H*W+1)
for i in range(H):
    ar=acinput()
    for j,sar in enumerate(ar):
        Ad[sar]=np.array((i,j))

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

for x in range(1, H*W+1):
    dp[x][x]=0

for x in range(1,H*W+1):
    y=x+D
    while True:
        if y > H*W:
            break
        #print(x,y)
        tmp = Ad[y]-Ad[y-D]
        S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        dp[x][y]=dp[x][y-D]+S
        y+=D
        

#print(np.array(dp))

Q=int(input())
for i in range(Q):
    l,r=acinput()
    print(dp[l][r])

Submission status: Runtime Error

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

# queryがたくさんある系
# query一つにつきO(1)ぐらいで応答しないと行けない→前処理の必要あり

# あるマスについてはD倍したマスだけ把握しておけばいいんじゃない？
'''
D=2
1 4 3
2 5 7
8 9 6
'''
# だったらstart=1,2において、移動のスコアの累積和を入れていく
# Qに回答時は、L%D番目のstartの累積和において、L//Dにおいて累積和の差を求めれば良い
# ピッタリDだった場合に面倒なので-0.5して置くのは良いかもしれない

from collections import defaultdict
from itertools import accumulate
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def get_cost(i, j, x, y):
    return abs(x - i) + abs(y - j)


H, W, D = read_ints()
A = read_matrix(H)
ruiseki = defaultdict(lambda: [])
num_to_co = {}

for i, a in enumerate(A):
    for j, aa in enumerate(a):
        num_to_co[aa] = (i, j)

for num in range(1, D + 1):
    pre_i, pre_j = num_to_co[num]
    pre_num = num
    ruiseki[num].append(0)
    while W * H >= pre_num + D:
        now_num = pre_num + D
        i, j = num_to_co[now_num]
        cost = get_cost(pre_i, pre_j, i, j)
        ruiseki[num].append(cost)
        # 必要なもの、前のi,j今のi,j 今の番号
        # 更新するもの 前のi,j←今のi,j 今の番号を次の番号に
        pre_i, pre_j = i, j
        pre_num = now_num

    ruiseki[num] = list(accumulate(ruiseki[num]))
# print(ruiseki)

# Qに答える番だ
Q = int(input())
for _ in range(Q):
    L, R = read_ints()
    tmp = ruiseki[L % D if L % D != 0 else (L // D)]
    # print(tmp)
    # print((R - 1) // D, (L - 1) // D)
    print(tmp[(R - 1) // D] - tmp[(L - 1) // D])

Submission status: Runtime Error

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

# queryがたくさんある系
# query一つにつきO(1)ぐらいで応答しないと行けない→前処理の必要あり

# あるマスについてはD倍したマスだけ把握しておけばいいんじゃない？
'''
D=2
1 4 3
2 5 7
8 9 6
'''
# だったらstart=1,2において、移動のスコアの累積和を入れていく
# Qに回答時は、L%D番目のstartの累積和において、L//Dにおいて累積和の差を求めれば良い
# ピッタリDだった場合に面倒なので-0.5して置くのは良いかもしれない

from collections import defaultdict
from itertools import accumulate
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def get_cost(i, j, x, y):
    return abs(x - i) + abs(y - j)


H, W, D = read_ints()
A = read_matrix(H)
ruiseki = defaultdict(lambda: [])
num_to_co = {}

for i, a in enumerate(A):
    for j, aa in enumerate(a):
        num_to_co[aa] = (i, j)

for num in range(1, D + 1):
    pre_i, pre_j = num_to_co[num]
    pre_num = num
    ruiseki[num].append(0)
    while W * H >= pre_num + D:
        now_num = pre_num + D
        i, j = num_to_co[now_num]
        cost = get_cost(pre_i, pre_j, i, j)
        ruiseki[num].append(cost)
        # 必要なもの、前のi,j今のi,j 今の番号
        # 更新するもの 前のi,j←今のi,j 今の番号を次の番号に
        pre_i, pre_j = i, j
        pre_num = now_num

    ruiseki[num] = list(accumulate(ruiseki[num]))
# print(ruiseki)

# Qに答える番だ
Q = int(input())
for _ in range(Q):
    L, R = read_ints()
    tmp = ruiseki[L % D if L % D != 0 else L // D]
    # print(tmp)
    # print((R - 1) // D, (L - 1) // D)
    print(tmp[(R - 1) // D] - tmp[(L - 1) // D])

Submission status: Runtime Error

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

for i in range(h):
    for j in range(w):
        ans[l[i][j]%d][l[i][j]//d] = (l[i][j],i,j)

count =[0]*(h*w+1)
for i in range(2,len(ans[0])):
    if ans[0][i] == 0:
        break
    count[ans[0][i][0]] = count[ans[0][i-1][0]] + abs(ans[0][i][1]-ans[0][i-1][1])+abs(ans[0][i][2]-ans[0][i-1][2])
for i in range(1,d):
    for j in range(1,len(ans[i])):
        if ans[i][j] == 0:
            break
        count[ans[i][j][0]] = count[ans[i][j-1][0]] + abs(ans[i][j][1]-ans[i][j-1][1])+abs(ans[i][j][2]-ans[i][j-1][2])

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])

Submission status: Runtime Error

Solution code:
h,w,d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
q=int(input())
b=[list(map(int, input().split())) for i in range(q)]
import collections
from collections import defaultdict
x=defaultdict(int)



for i in range(h):
    for j in range(w):
        x[i,j]=a[i][j]
x1=sorted(x.items(),key=lambda x:x[1])

ans=[[0]*(-(h*w//-d)) for i in range(d)]


for i in range(d):
    count=0
    for j in range(1,-(h*w//-d)-1):
        count+=abs(x1[i+(j-1)*d][0][0]-x1[i+j*d][0][0])
        count+=abs(x1[i+(j-1)*d][0][1]-x1[i+j*d][0][1])
        ans[i][j]+=count

for i in range(q):
    u=(b[i][0]-1)%d
    u1=(b[i][0]-u)//d
    v=(b[i][1]-b[i][0])//d

    print(ans[u][u1+v]-ans[u][u1])

Submission status: Runtime Error

Solution code:
h,w,d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
q=int(input())
b=[list(map(int, input().split())) for i in range(q)]
import collections
from collections import defaultdict
x=defaultdict(int)



for i in range(h):
    for j in range(w):
        x[i,j]=a[i][j]
x1=sorted(x.items(),key=lambda x:x[1])

ans=[[0]*(-(h*w//-d)) for i in range(d)]


for i in range(d):
    count=0
    for j in range(1,-(h*w//-d)):
        if i+j*d>=h*w:
            continue
        count+=abs(x1[i+(j-1)*d][0][0]-x1[i+j*d][0][0])
        count+=abs(x1[i+(j-1)*d][0][1]-x1[i+j*d][0][1])
        ans[i][j]+=count

for i in range(q):
    u=(b[i][0]-1)%d
    u1=(b[i][0]-u)//d
    v=(b[i][1]-b[i][0])//d

    print(ans[u][u1+v]-ans[u][u1])

Submission status: Runtime Error

Solution code:
import math
h, w, d = list(map(int, input().split()))
grid = []
num = [[] for i in range(h*w+1)]
graph = [[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    for j in range(w):
        num[grid[i][j]]=[j+1, i+1]
k = math.ceil((h*w) / d)
#initialize
cost = [[0 for i in range(k)] for j in range(d)]
for i in range(d):
    cost[i][0] = 0
for i in range(d + 1,h*w+1):
    x, y = num[i]
    prex, prey = num[i - d]
    cost[i % d][i//d] = abs(prex - x) + abs(prey - y)
    cost[i % d][i//d] += cost[i % d][(i - d)// d]  
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r%d][r//d] - cost[l%d][l//d])

Submission status: Runtime Error

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

#N, *a = map(int, open(0).read().split())


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

    def saiki(n, d, r):
        # print(n, d, r)
        if n == r:
            return 0
        elif num[n] > 0:
            return num[n] + saiki(n + d, d, r)
        else:
            tmp = abs(B[n][0] - B[n + d][0]) + abs(B[n][1] - B[n + d][1])
            num[n] = tmp
            # print(tmp)
            return num[n] + saiki(n + d, d, r)

    for i in range(h):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            B[t] = [i, j]

    q = int(input())

    ans = 0
    for j in range(q):
        l, r = map(int, input().split())

        # print("#", l, d, r, "#")
        if h == w and h == 1:
            ans = 0
        else:
            ans = saiki(l, d, r)
        print(ans)


main()

Submission status: Runtime Error

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

#N, *a = map(int, open(0).read().split())


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

    def saiki(n, d, r):
        # print(n, d, r)
        if n == r:
            return 0
        elif num[n] > 0:
            return num[n] + saiki(n + d, d, r)
        else:
            tmp = abs(B[n][0] - B[n + d][0]) + abs(B[n][1] - B[n + d][1])
            num[n] = tmp
            # print(tmp)
            return num[n] + saiki(n + d, d, r)

    for i in range(h):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            B[t] = [i, j]

    q = int(input())

    ans = 0
    for j in range(q):
        l, r = map(int, input().split())

        # print("#", l, d, r, "#")
        ans = saiki(l, d, r)

        if h == w and h == 1:
            ans = 0
        print(ans)


main()

Submission status: Runtime Error

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

#N, *a = map(int, open(0).read().split())


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

    def saiki(n, d, r):
        # print(n, d, r)
        if n == r:
            return 0
        elif num[n] > 0:
            return num[n] + saiki(n + d, d, r)
        else:
            tmp = abs(B[n][0] - B[n + d][0]) + abs(B[n][1] - B[n + d][1])
            num[n] = tmp
            # print(tmp)
            return num[n] + saiki(n + d, d, r)

    for i in range(h):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            B[t] = [i, j]

    q = int(input())
    L = []
    R = []

    ans = 0
    for j in range(q):
        l, r = map(int, input().split())
        # print("#", l, d, r, "#")
        ans = saiki(l, d, r)

        print(ans)


main()

Submission status: Runtime Error

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

#N, *a = map(int, open(0).read().split())


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

    def saiki(n, d, r):
        # print(n, d, r)
        if n == r:
            return 0
        elif num[n] > 0:
            return num[n] + saiki(n + d, d, r)
        else:
            tmp = abs(B[n][0] - B[n + d][0]) + abs(B[n][1] - B[n + d][1])
            num[n] = tmp
            # print(tmp)
            return num[n] + saiki(n + d, d, r)

    for i in range(h):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            B[t] = [i, j]

    q = int(input())
    L = []
    R = []

    ans = 0
    for j in range(q):
        l, r = map(int, input().split())
        # print("#", l, d, r, "#")
        ans = saiki(l, d, r)

        print(ans)


main()

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy as sp
import matplotlib.pyplot as plt
import sys
input = sys.stdin.readline

#N, *a = map(int, open(0).read().split())


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

    def saiki(n, d, r):
        # print(n, d, r)
        if n == r:
            return 0
        elif num[n] > 0:
            return num[n] + saiki(n + d, d, r)
        else:
            tmp = abs(B[n][0] - B[n + d][0]) + abs(B[n][1] - B[n + d][1])
            num[n] = tmp
            # print(tmp)
            return num[n] + saiki(n + d, d, r)

    for i in range(h):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            B[t] = [i, j]

    q = int(input())
    L = []
    R = []

    ans = 0
    for j in range(q):
        l, r = map(int, input().split())
        # print("#", l, d, r, "#")
        ans = saiki(l, d, r)

        print(ans)


main()

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split(" "))
grid = list()
d = dict()
for y in range(1, H+1):
    line = list(map(int, input().split(" ")))
    for x in range(1, W+1):
        num = line[x-1]
        d[num] = (x, y)

memo = dict()


def get_cost(num):
    if num <= D:
        return 0
    if num in memo:
        return memo[num]
    pos_x, pos_y = d[num]
    pos_x_1, pos_y_1 = d[num-D]
    cost = get_cost(num-D) + abs(pos_x - pos_x_1) + abs(pos_y - pos_y_1)
    memo[num] = cost
    return cost


Q = int(input())
exams = list()
for _ in range(Q):
    l, r = [int(i) for i in input().split(" ")]
    print(get_cost(r) - get_cost(l))

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split(" "))
grid = list()
d = dict()
for y in range(1, H+1):
    line = list(map(int, input().split(" ")))
    for x in range(1, W+1):
        num = line[x-1]
        d[num] = (x, y)

memo = dict()


def get_cost(num):
    if num <= D:
        return 0
    if num in memo:
        return memo[num]
    pos_x, pos_y = d[num]
    pos_x_1, pos_y_1 = d[num-D]
    cost = get_cost(num-D) + abs(pos_x - pos_x_1) + abs(pos_y - pos_y_1)
    memo[num] = cost
    return cost


Q = int(input())
exams = list()
for _ in range(Q):
    exams.append([int(i) for i in input().split(" ")])

for exam in exams:
    l, r = exam
    print(get_cost(r) - get_cost(l))