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:
# coding:utf-8

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W + 1, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w,d = map(int, input().split())
dd = {}
for hi in range(h):
    line = list(map(int, input().split()))
    for wi in range(w):
        dd[line[wi]] = (hi, wi)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

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

    h1,w1 = dd[i]
    h2,w2 = dd[i-d]
    acc[i] = acc[i-d] + abs(h1-h2) + abs(w1-w2)

for (l,r) in lr:
    print(acc[r] - acc[l])

Submission status: Accepted

Solution code:
H, W, D = (int(i) for i in input().split())

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

for i in range(H):
    ww = [int(j) for j in input().split()]
    for j in range(len(ww)):
        dd[(ww[j] - 1)%D][(ww[j] - 1)//D] = (i, j)

dds = [[0] * (H * W // D + 1) for i in range(D)]

for i in range(D):
    for j in range(1, len(dd[i])):
        if dd[i][j] != (-1, -1):
            temp = abs(dd[i][j][0] - dd[i][j-1][0]) + abs(dd[i][j][1] - dd[i][j-1][1])
            dds[i][j] = dds[i][j-1] + temp
        else:
            pass

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

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
P = [[] for i in range(H * W)]
for i in range(H):
  for j, a in enumerate(input().split()):
    P[int(a) - 1] = [i, j]
C = [[0 for j in range(-(-H * W // D) + 1)] for i in range(D)]
for i in range(H * W - D):
  C[i % D][i // D + 1] = abs(P[i][0] - P[i + D][0]) + abs(P[i][1] - P[i + D][1])
for i in range(D):
  for j in range(1, -(-H * W // D) + 1):
    C[i][j] += C[i][j - 1]
Q = int(input())
for i in range(Q):
  L, R = [int(x) - 1 for x in input().split()]
  print(C[R % D][R // D] - C[L % D][L // D])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
from pprint import pprint

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

xy = {}
for h in range(H):
    for w in range(W):
        xy[A[h][w]] = (h,w)

xy[0] = xy[D]

width = math.ceil(H*W/D)
rui_xy = [[0 for _ in range(width+1)] for _ in range(D)]
for d in range(D):
    rui_cost = 0
    x,y = xy[d]
    for w in range(width+1):
        if w*D+d > H*W:
            break
        i,j = xy[w*D+d]
        rui_cost += abs(x-i) + abs(y-j)
        rui_xy[d][w] = rui_cost
        x,y = i,j

for l,r in LR:
    if l == r:
        print(0)
        continue

    print(rui_xy[r % D][r//D] - rui_xy[l % D][l//D])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0

Submission status: Accepted

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

MaxD = D * ((H*W)//D)
Cost = [[0] for i in range(D)]
for i in range(D):
    now = (D if i == 0 else i)
    nowx, nowy = C[now]
    while now + D <= H * W:
        nextx, nexty = C[now+D]
        MP = abs(nowx - nextx) + abs(nowy - nexty)
        Cost[i].append(Cost[i][-1] + MP)
        now += D
        nowx, nowy = nextx, nexty

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

Submission status: Accepted

Solution code:
h,w,d=map(int, input().split())
m=[list(map(int, input().split())) for i in range(h)]
b=[0]*(h*w)
for i in range(h):
    for j in range(w):
        b[m[i][j]-1]=[i,j]
dp=[0]*(h*w)
for i in range(d,h*w):
    dp[i]=dp[i-d]+abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
n=int(input())
for i in range(n):
    x,y=map(int, input().split())
    print(dp[y-1]-dp[x-1])

Submission status: Accepted

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

for i in range(h):#h:高さ
    a.append([int(m) for m in input().split()])

q = int(input())
lr = []
for i in range(q):#h:高さ
    lr.append([int(m) for m in input().split()])

rea = []
for i in range(h * w):
    rea.append([])


for i in range(h):
    for j in range(w):
        rea[w*i+j].append(a[i][j])
        rea[w*i+j].append(i)
        rea[w*i+j].append(j)

rea.sort()

pre = []
for i in range(h*w):
    pre.append([])
p = 0
for i in range(h):
    if p == 1:
        break
    for j in range(w):
        if w * i + j + 1 <= d:
            lmn = 0
            pre[w * i + j].append(lmn)

            for k in range(0,h*w,d):
                if w*i+j + d + k < h*w:
                    lmn += abs(rea[w*i+j + k][1] - rea[w*i+j+d + k][1]) + abs(rea[w*i+j + k][2]- rea[w*i+j+d + k][2])
                    pre[w*i+j].append(lmn)
                else:
                    break
        else:
            p = 1
            break

for i in range(q):
    print(pre[(lr[i][0] - 1) % d][(lr[i][1] - 1)//d] - pre[(lr[i][0] - 1) % d][(lr[i][0] - 1)//d])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
data=[]
for i in range(1,H+1):
    tmp=list(map(int,input().split()))
    for j in range(1,W+1):
        data.append([i,j,tmp[j-1]])

data.sort(key=lambda x:x[2])

ruiseki=[]
for i in range(D):
    tmp=[0]
    j=i+D
    while(j<H*W):
        tmp.append( abs(data[j][0]-data[j-D][0]) +abs(data[j][1]-data[j-D][1]) +tmp[-1])
        j+=D
    ruiseki.append(tmp)

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

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]

nc = dict()
for row in range(h):
    for col in range(w):
        v = A[row][col]
        nc[v] = (row, col)

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

c_sums = [[0] for _ in range(d)]
for r in range(d):
    k = 0
    if r == 0: k = 1
    while r + (k + 1) * d <= h * w:
        i, j = nc[r + k * d]
        x, y = nc[r + (k + 1) * d]
        t = c_sums[r][-1] + abs(x - i) + abs(y - j)
        c_sums[r].append(t)
        k += 1

for lr in lrs:
    l, r = lr
    ld, rest = divmod(l, d)
    rd = r // d
    if rest == 0:
        ld -=1
        rd -=1
    print(c_sums[rest][rd] - c_sums[rest][ld])

Submission status: Accepted

Solution code:
#座標も数値も全部0-indexedに直す
H,W,D=map(int,input().split())
coordinate = [None for _ in range(H*W)]
for i in range(H):
    raw = list(map(int,input().split()))
    for j in range(W):
        coordinate[raw[j]-1] = (i,j)
l = H*W//D + 2
cumm = [[0 for _ in range(l)] for _ in range(D)]
for i in range(H*W):
    q,r = divmod(i,D)
    if q==0:
        continue
    #q>0
    x1,y1 = coordinate[i]
    x0,y0 = coordinate[i-D]
    distance = abs(x1-x0) + abs(y1-y0)
    cumm[r][q] = cumm[r][q-1] + distance
Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    q0,r0 = divmod(L-1,D)
    q1,r1 = divmod(R-1,D)
    print(cumm[r1][q1]-cumm[r0][q0])

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W, D = inpl()
S = dict([])
for i in range(H):
    a = inpl()
    for j in range(W):
        S[a[j]] = [i,j]

dist = [[0] for i in range(D+1) ]
for i in range(1,D+1):
    for j in range(1,1+(H*W-i)//D):
        dist[i].append(dist[i][-1] +\
        (abs(S[i+j*D][0]-S[i+(j-1)*D][0])+abs(S[i+j*D][1]-S[i+(j-1)*D][1])))
Q = int(input())
ans = []
for i in range(Q):
    l, r = inpl()
    mod = l % D
    if mod == 0 : mod = D
    l, r = (l-mod)//D, (r-mod)//D
    ans.append(dist[mod][r]-dist[mod][l])
for i in ans:
    print(i)

Submission status: Accepted

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

s = [None for _ in range(d)]
for i in range(min(d, h * w - d + 1)):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

Submission status: Accepted

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

memo = [[] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        memo[a[i][j]-1].append((i, j))

cost = [0 for i in range(h*w)]
for t in range(d, h*w):
    i, j = memo[t-d][0]
    x, y = memo[t][0]
    cost[t] = abs(x-i) + abs(y-j)
for s in range(d):
    for i in range(s, h*w-d, d):
        cost[i+d] += cost[i]

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

Submission status: Accepted

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

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

costs = [[] for i in range(D)]
for i in range(H*W+1):
    if i <= D:
        costs[i%D].append(0)
    else:
        x1,y1 = places[i-D]
        x2,y2 = places[i]
        c = abs(x1-x2) + abs(y1-y2)
        costs[i%D].append(costs[i%D][-1] + c)

ans = []
for l,r in qs:
    m = l%D
    a = costs[m][r//D] - costs[m][l//D]
    ans.append(a)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# パスを計算
h,w,d = li()
grid = []
dic = {}
for i in range(h):
    row = list(li())
    for j in range(w):
        dic.update({row[j]: (i,j)})

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

for i in range(d+1,h*w+1):
    dist[i] = dist[i-d] + abs(dic[i][0] - dic[i-d][0]) + abs(dic[i][1] - dic[i-d][1])
    
q = ni()
for _ in range(q):
    l,r = li()
    print(dist[r] - dist[l])

Submission status: Accepted

Solution code:
def ABC089D():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(H)]
    Q = int(input())
    LR = [list(map(int, input().split())) for i in range(Q)]
    number_place = [[] for i in range(H * W)]
    for i in range(H):
        for j in range(W):
            number_place[A[i][j] - 1] = [i, j]
    d = [0 for i in range(H * W)]
    for i in range(D):
        d[i] = 0
    for i in range(D, H * W):
        past_y = number_place[i - D][0]
        past_x = number_place[i - D][1]
        now_y = number_place[i][0]
        now_x = number_place[i][1]
        d[i] = abs(now_x - past_x) + abs(now_y - past_y) + d[i - D]
    for i, j in LR:
        print(d[j - 1] - d[i - 1])
ABC089D()

Submission status: Accepted

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

Numbers = {}
for h in range(H):
    for w in range(W):
        Numbers[A[h][w]] = (h, w)

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

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

Submission status: Accepted

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

x=[[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        x[a[i][j]-1]=[i,j]
z=[0 for _ in range(h*w)]
for i in range(d):
    for j in range(i+d,h*w,d):
        z[j]=z[j-d]+abs(x[j][0]-x[j-d][0])+abs(x[j][1]-x[j-d][1])
#print(x)
#print(z)
for t in lr:
    print(z[t[1]-1]-z[t[0]-1])

Submission status: Accepted

Solution code:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])

Submission status: Accepted

Solution code:
#%% D
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
a_dic = {}
for i, row in enumerate(A):
    for j, a in enumerate(row):
        a_dic[a] = (i, j)

dist = [0] * (H * W + 1)
for i in range(1, H * W - D + 1):
    px, py = a_dic[i]
    nx, ny = a_dic[i + D]
    dist[i + D] = abs(nx - px) + abs(ny - py)

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

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

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
h,w,d=I()
H={}
W={}
for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
x=1+h*w
s=[0 for _ in [0]*x]
for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

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

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
h,w,d=I()
H={}
W={}
for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
x=1+h*w
s=[0 for _ in range(x)]
for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

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

Submission status: Accepted

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

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)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {}
for num in range(1, H*W+1):
    if num <= D:
        cost_table[num] = 0
    else:
        i, j = num_pos[num-D]
        x, y = num_pos[num]
        cost_table[num] = abs(i - x) + abs(j - y) + cost_table[num-D]

for l, r in LR:
    print(cost_table[r] - cost_table[l])

Submission status: Accepted

Solution code:
import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
basyo = [[0,0] for i in range(H*W)]
for i in range(W):
  for j in range(H):
    basyo[int(a[j][i])-1] = [j,i]
Q = int(input())
b = [input().split() for l in range(Q)]
ans = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    i += D
    if i >= H*W:
      break
    memo[i] = memo[i-D]  + abs(basyo[i][0] - basyo[i-D][0]) + abs(basyo[i-D][1] - basyo[i][1])
b = np.array(b)
b = np.int64(b)
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])

Submission status: Accepted

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

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

costs = [0]*(h*w+1)
for x in range(d+1, h*w+1):
    i_prev, j_prev = a_and_pos[x-d]
    i, j = a_and_pos[x]
    costs[x] = costs[x-d] + abs(i-i_prev) + abs(j-j_prev)
# print(costs)

for l, r in lr:
    print(costs[r] - costs[l])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

H, W, D = ds_in()
A_arr = []
for i in range(H):
    A = ds_in()
    for j, a in enumerate(A):
        A_arr.append((a, [i, j]))

A_arr.sort(key=lambda x: x[0])

Q = d_in()
LR_list = []
for _ in range(Q):
    LR_list.append(ds_in())

Costs = [0] * (H*W)
for i in range(1, D+1):
    s = i
    s_xy = A_arr[s-1][1]
    cost, next_cost = 0, 0
    Costs[s-1] = cost
    s += D
    while s <= H * W:
        xy = A_arr[s-1][1]
        next_cost = abs(xy[0] - s_xy[0]) + abs(xy[1] - s_xy[1])
        cost += next_cost
        Costs[s-1] = cost
        s_xy = xy.copy()
        s += D

for q in LR_list:
    print(Costs[q[1] - 1] - Costs[q[0] - 1])

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

h,w,d = ai()
ph = [0 for _ in range(h*w + 1)]
pw = [0 for _ in range(h*w + 1)]

for i in range(h):
    a = ai()
    for j in range(w):
        ph[a[j]] = i
        pw[a[j]] = j


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


q = int(input())
ans = []
for _ in range(q):
    l,r = ai()
    ans.append(score[r]-score[l])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

h,w,d = ai()
ph = [0 for _ in range(h*w + 1)]
pw = [0 for _ in range(h*w + 1)]

for i in range(h):
    a = ai()
    for j in range(w):
        ph[a[j]] = i
        pw[a[j]] = j


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


q = int(input())
for _ in range(q):
    l,r = ai()
    print(score[r]-score[l])

Submission status: Accepted

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

# aij to (i, j)
a = {}
for i in range(h):
    ai = list(map(int, input().split()))
    for j in range(w):
        a[ai[j]] = (i + 1, j + 1)

q = int(input())

mana = [0 for i in range(h * w + 1)]
for i in range(1, h * w + 1):
    if i + d > h * w:
        break

    y, x = a[i]
    ny, nx = a[i + d]
    mana[i + d] = mana[i] + abs(y - ny) + abs(x - nx)

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

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

H, W, D = map(int, raw_input().split())
m = [0] * (H * W + 1)
for i in range(H):
    A = map(int, raw_input().split())
    for j in range(W):
        m[A[j]] = (i, j)

DP = [0] * D

for i in range(D, H * W):
    x1, y1 = m[i + 1]
    x2, y2 = m[i + 1 - D]
    dist = abs(x1 - x2) + abs(y1 - y2)
    DP.append(DP[i - D] + dist)

Q = input()

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

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

H, W, D = map(int, raw_input().split())
m = [0] * (H * W + 1)
for i in range(H):
    A = map(int, raw_input().split())
    for j in range(W):
        m[A[j]] = (i, j)

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

for i in range(D, H * W):
    x1, y1 = m[i + 1]
    x2, y2 = m[i + 1 - D]
    dist = abs(x1 - x2) + abs(y1 - y2)
    ls = DP[i % D]
    ls.append(ls[-1] + dist)

Q = input()

for i in range(Q):
    L, R = map(int, raw_input().split())
    ls = DP[(R - 1) % D]
    print ls[(R - 1) / D] - ls[(L - 1) / D]

Submission status: Accepted

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

A = {0: (0, 0)}

for i in range(H):
    A_list = list(map(int, input().split()))

    for j in range(1, len(A_list) + 1):
        A[A_list[j - 1]] = (i, j)

serial = {}
for m in range(D):
    t_x = A[m][0]
    t_y = A[m][1]

    t = 0
    tmp_sum = 0
    serial[m] = []
    serial[m].append(tmp_sum)
    while(m + (t + 1) * D <= H * W):
        t += 1
        x = A[m + t * D][0]
        y = A[m + t * D][1]
        tmp_sum += abs(x - t_x) + abs(y - t_y)
        serial[m].append(tmp_sum)
        t_x = x
        t_y = y

Q = int(input())
ans = 0
# print(serial)
L = []
R = []
for i in range(Q):
    tL, tR = map(int, input().split())
    L.append(tL)
    R.append(tR)

for i in range(Q):
    tL = L[i]
    tR = R[i]
    print(serial[tL % D][tR // D] - serial[tL % D][tL // D])

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, D = map(int, input().split())
B = {}
for i in range(H):
    Ai = [int(x) for x in input().split()]
    for j, Aij in enumerate(Ai):
        B[Aij] = (i, j)
costs = defaultdict(list)

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

Q = int(input())
for i in range(Q):
    Li, Ri = map(int, input().split())
    print(costs[Ri] - costs[Li])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,D = inpl()

dd = defaultdict(int)
for y in range(H):
	row = inpl()
	for x,n in enumerate(row):
		dd[n] = [x,y]

S = [0]*D
for k in range(1,D+1):
	i = k+D
	tmpli = [0]
	tmp = 0
	while i <= H*W:
		x1,y1 = dd[i-D]
		x2,y2 = dd[i]
		tmp += abs(x1-x2)+abs(y1-y2)
		tmpli.append(tmp)
		i += D
	S[i%D] = tmpli


Q = int(input())
for _ in range(Q):
	L,R = inpl()
	k = L%D
	l,r = (L-k)//D, (R-k)//D
	if k==0:
		l -= 1
		r -= 1
	print(S[k][r]-S[k][l])

Submission status: Accepted

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

m={}
for i in range(1,h+1):
  for (j,k) in enumerate(map(int,input().split())):
    m[k]=(i,j+1)

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

for _ in range(int(input())):
  a,b=map(int,input().split())
  print(s[b]-s[a])

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
px = [0 for k in range(H*W+D+1)]
py = [0 for k in range(H*W+D+1)]
S = [list(map(int,input().split())) for k in range(H)]

for j in range(W):
    for i in range(H):
        px[S[i][j]] = i
        py[S[i][j]] = j

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

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

Submission status: Accepted

Solution code:
import numpy as np
H, W, D = map(int, input().split())
grid = np.array([[0, 0]] * (H * W))
for i in range(H):
    Ai = list(map(int, input().split()))
    for j in range(W):
        grid[Ai[j] - 1] = [i, j]
Q = int(input())
tasks = [list(map(int, input().split())) for _ in range(Q)]

accum = [0] * (H*W)
for i in range(H * W):
    if i >= D:
        accum[i] = accum[i - D] + abs(grid[i][0] - grid[i - D][0]) + abs(grid[i][1] - grid[i - D][1])

for q in range(Q):
    Li, Ri = tasks[q]
    print(accum[Ri - 1] - accum[Li - 1])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
P = {}
for x in range(W):
    for y in range(H):
        P[A[y][x]] = (x, y)

# 倍数軸累積和
S = [0] * (H*W+1)
for n in range(1, H*W+1):
    if n + D > len(S) - 1:
        continue
    S[n + D] = abs(P[n][0] - P[n+D][0]) + abs(P[n][1] - P[n+D][1])

for n in range(1, H*W+1):
    if n + D > len(S) - 1:
        continue
    S[n + D] += S[n]

# クエリに答えていく
Q = int(input())
for q in range(Q):
    Li, Ri = map(int, input().split())
    print(S[Ri] - S[Li])

Submission status: Accepted

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    A ={}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            A[int(input_raw[j])] = (i, j)

    D_map = {}
    for x in range(1, H * W + 1):
        if x % D not in D_map:
            D_map[x % D] = [(A[x], 0)]
        else:
            (p, q) = D_map[x % D][(x / D) - (2 if x % D == 0 else 1)][0]
            pre_d = D_map[x % D][(x / D) - (2 if x % D == 0 else 1)][1]
            d = abs(p - A[x][0]) + abs(q - A[x][1])
            D_map[x % D].append((A[x], d + pre_d))

    input_raw = read_func().strip().split()
    [Q] = [long(input_raw[0])]
    for i in range(Q):
        input_raw = read_func().strip().split()
        [L, R] = [long(input_raw[0]), long(input_raw[1])]
        l = L % D
        print D_map[l][R/D - (1 if R % D == 0 else 0)][1] - D_map[l][L/D - (1 if L % D == 0 else 0)][1]



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#memoryが少ない例。下手に２次元とかでやるより良いってこと？
H, W, D = [int(i) for i in input().split()]
px = [0] * 90001
py = [0] * 90001

for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        px[v] = j
        py[v] = i

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

Q = int(input())

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

Submission status: Accepted

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

for i in range(H):
  tmp = list(map(int,input().split()))
  for j in range(len(tmp)):
    x = tmp[j]
    arr[x][0], arr[x][1] = i, j

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

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

Submission status: Accepted

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

field = []

for i in range(h):
	field.append(map(int,raw_input().split()))

distance = [0 for i in range(90001)]


n = int(input())

arr = [[] for i in range(90001)]

inputs = []

for i in range(n):
	inputs.append(map(int,raw_input().split()))


for i in range(h):
	for j in range(w):
		arr[field[i][j]] = [i+1,j+1]

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


for i in range(n):
	l,r = inputs[i]

	print distance[r]-distance[l]

Submission status: Accepted

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

H,W,D = map(int, sdin().split())
A = []
for h in range(H):
    A.append(list(map(int, sdin().split())))
Q = int(sdin())
RL = []
for q in range(Q):
    RL.append(tuple(map(int, sdin().split())))


codn = {}
for h in range(H):
    for w in range(W):
        codn[A[h][w]] = (h+1, w+1)
        
# mod D上での累積和
cums = []
for d in range(D):
    cum = []
    res = D
    if d!=0:
        res = d
    
    cum = [0]
    while res+D <= H*W:
        prev = codn[res]
        nex = codn[res+D]
        cost = abs(nex[0]-prev[0]) + abs(nex[1]-prev[1])
        cum.append(cum[-1]+cost)
        
        res += D
    
    cums.append(cum)
    
# 各クエリの処理
ans = 0
for query in range(Q):
    q = RL[query]
    mod = q[0] % D
    start = (q[0]-mod) // D
    last = (q[1]-mod) // D
    if mod == 0:
        start -= 1
        last -= 1
    
    ans = cums[mod][last] - cums[mod][start]   
    
    print(ans)