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:
from math import ceil
h,w,d=map(int,input().split())
x=ceil((h*w)/d)
num=[[[-1,-1] for j in range(x)] for i in range(d)]#あまりで場合分け(1→0)
mp=[[0]*x for i in range(d)]
a=[list(map(int,input().split())) for i in range(h)]
for i in range(h):
    for j in range(w):
        k,l=a[i][j]%d,a[i][j]//d
        if k==0:
            num[d-1][l-1]=[i,j]
        else:
            num[k-1][l]=[i,j]
for i in range(d):
    for j in range(x):
        if j!=x-1:
            if num[i][j+1]!=[-1,-1]:
                mp[i][j+1]+=(mp[i][j]+abs(num[i][j+1][0]-num[i][j][0])+abs(num[i][j+1][1]-num[i][j][1]))
            else:
                break
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    if l%d!=0:
        e,f=l//d,r//d
    else:
        e,f=l//d-1,r//d-1
    g= d-1 if l%d==0 else l%d-1
    if e==0:
        print(mp[g][f])
    else:
        print(mp[g][f]-mp[g][e])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
r = [None for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        r[a[i][j]] = (i,j)
#print(r)

c = [0 for i in range(h*w+1)]
for i in range(d+1,h*w+1):
    c[i] = c[i-d] + abs(r[i][0]-r[i-d][0]) + abs(r[i][1]-r[i-d][1])
#print(c)
q = int(input())
for _ in range(q):
    x,y = map(int,input().split())
    print(c[y]-c[x])

Submission status: Accepted

Solution code:
#089_D
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
idx = {}
for x in range(0, h):
    for y in range(0, w):
        idx[a[x][y]] = (x, y)
        
dp = [0 for _ in range(h*w+1)]
for i in range(0, h*w+1):
    if i <= d:
        continue
    x, y = idx[i]
    x_, y_ = idx[i-d]
    dp[i] = dp[i-d] + abs(x-x_) + abs(y-y_)
        
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(dp[r] - dp[l])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
peak = H * W
L = [[0 for j in range(i+1, peak+1, D)] for i in range(D)]
dd = {}
for i in range(H):
  line = list(map(int, input().split()))
  for j in range(W):
    dd[line[j]] = [i, j]
for m in range(D):
  ddd = (peak - m - 1) // D
  for k in range(1, ddd + 1):
    dist = abs(dd[k*D+m+1][0] - dd[(k-1)*D+m+1][0])
    dist += abs(dd[k*D+m+1][1] - dd[(k-1)*D+m+1][1])
    L[m][k] = L[m][k-1] + dist
Q = int(input())
for i in range(Q):
  pL, pR = map(int, input().split())
  l, r = (pL - 1) // D, (pR - 1) // D
  mod = (pL - 1) % D
  print(L[mod][r] - L[mod][l])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W, D = map(int, input().split(' '))
n_position_dict = {}

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

diffs = [1 for _ in range(H*W+1)]
for i in range(D+1, H*W+1):
    h, w = n_position_dict[i]
    next_h, next_w = n_position_dict[i-D]
    diffs[i] = diffs[i-D] + abs(h - next_h) + abs(w - next_w)
# print(diffs)

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

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)]
size=h*w+1

B=[[] for _ in range(size)]
for i in range(h):
    for j in range(w):
        B[A[i][j]]=[i,j]

DP=[0]*size
for i in range(d+1,size):
    x,y=B[i]
    z,w=B[i-d]
    DP[i]=DP[i-d]+abs(x-z)+abs(y-w)

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

Submission status: Accepted

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

B=[[] for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        B[A[i][j]]=[i,j]

DP=[0]*(h*w+1)
for i in range(d+1,h*w+1):
    x,y=B[i]
    z,w=B[i-d]
    DP[i]=DP[i-d]+abs(x-z)+abs(y-w)

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

Submission status: Accepted

Solution code:
from math import ceil

H, W, D = [int(i) for i in input().split()]
N = H*W
A = [[int(i) for i in input().split()] for _ in range(H)]

M = [0] * (N+1)
for h in range(H):
    for w in range(W):
        M[A[h][w]] = (h, w)

def f(s, t):
    if s==0: return 0
    return abs(s[0]-t[0])+abs(s[1]-t[1])


cumsum = [[0] for _ in range(D)]
for s in range(1, D+1):
    for i in range(s, N+1, D):
        if i <= D: cumsum[s-1].append(0)
        else: cumsum[s-1].append(cumsum[s-1][-1]+f(M[i-D], M[i]))

Q = int(input())
for _ in range(Q):
    L, R = [int(i) for i in input().split()]
    i = (L%D)-1
    if i==-1:
        print(cumsum[i][R//D] - cumsum[i][L//D])
    else:
        print(cumsum[i][ceil(R/D)] - cumsum[i][ceil(L/D)])

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))



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

info = []
for i in range(h):
    info.append(list(map(int, input().split())))
    
n = int(input())
qs = []
for i in range(n):
    qs.append(list(map(int, input().split())))
    
place = [[-1,-1] for i in range(h*w+1)]

for i in range(h):
    for j in range(w):
        place[info[i][j]] = [i,j]

lines = [[0] for i in range(d)]

for i in range(d):
    now = i
    dist = 0
    for j in range((h*w-i)//d):
        now += d
        p1 = place[now]
        p2 = place[now-d]
        dist += abs(p1[0]-p2[0])+abs(p1[1]-p2[1])
        lines[i].append(dist)

for i in range(n):
    k = qs[i][0]%d
    ll = qs[i][0]//d
    rr = qs[i][1]//d
    print(lines[k][rr]-lines[k][ll])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[list(map(int,input().split()))for i in range(h)]
num=[[]for i in range(h*w+1)]
num[0]=([0,0])
for i in range(h):
  for j in range(w):
    num[a[i][j]].extend([i,j])
cumsum=[0]*(h*w+1)
for i in range(d,h*w+1):
  x1,y1=num[i]
  x2,y2=num[i-d]
  cumsum[i]+=cumsum[i-d]+abs(x1-x2)+abs(y1-y2)
Q=int(input())
for _ in range(Q):
  x,y=map(int,input().split())
  print(cumsum[y]-cumsum[x])

Submission status: Accepted

Solution code:
import sys


def distance(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return abs(x2 - x1) + abs(y2 - y1)


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

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

S = [0] * (H * W + 1)
for i in range(1, H * W + 1):
    pi = max(0, i - D)
    S[i] = S[pi] + distance(P[pi], P[i])

ans = []
for q in sys.stdin.readlines():
    L, R = map(int, q.split())
    # ans.append(S[R] - S[L])
    print(S[R] - S[L])

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

Submission status: Accepted

Solution code:
import sys


def distance(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return abs(x2 - x1) + abs(y2 - y1)


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

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

S = [0] * (H * W + 1)
for i in range(1, H * W + 1):
    pi = max(0, i - D)
    S[i] = S[pi] + distance(P[pi], P[i])

ans = []
for q in sys.stdin.readlines():
    L, R = map(int, q.split())
    ans.append(S[R] - S[L])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# クエリが何回か飛んでくる→累積和か?

# 1回の実技試験での最大移動回数は、H*W/1 = 90000→愚直に計算すると無理。

# Dが実技試験によらず一定なので、移動後のマスから移動前のマスは分かる。

# 最初に各マスについて座標を調べて
# 次に移動前のマスとのマンハッタン距離を調べる
# しかし毎回の試験の魔力を愚直に計算すると、やはり90000程度が掛かって無理。

# P_i = i%Dからiまで移動して来るのに必要な魔力（i<=Dなら0）
# とすれば、毎回のクエリにはP_R - P_Lを出せばよく、定数時間で求まる

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

masu = h * w
h_coord = [-1] * masu  # 座標は0-indexで取る
w_coord = [-1] * masu

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

distance_sum = [0] * masu
for i in range(masu):
    if i < d:
        pass
    else:
        distance_sum[i] = distance_sum[i-d] + abs(h_coord[i] - h_coord[i-d]) + abs(w_coord[i] - w_coord[i-d])

q = int(input())

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

Submission status: Accepted

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

# W_max = (W)
fields = [0] * (W*H+1)
# 一列にして、保存しておこうか。
for i in range(H):
    rows = list(map(int, input().split()))
    for j,r in enumerate(rows):
        ind = i * W + j
        fields[r] = ind

def calc(l,r):
    indl = fields[l]
    hl = indl // W
    wl = indl % W
    indr = fields[r]
    hr = indr // W
    wr = indr % W
    d = abs(hl-hr) + abs(wl-wr)
    return d

# 累積
x = [[] for i in range(D)]  

for i in range(D):
    acc = 0
    x[i].append(0)
    for j in range(i, W*H+1, D):
        # print(j)
        acc += calc(j-D,j)
        x[i].append(acc)

# print(x)


### query
Q = int(input())
for _ in range(Q):
    L,R = map(int, input().split())
    amari = L%D
    print(x[amari][(R-amari)//D+1]-x[amari][(L-amari)//D+1])

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w,d = inm()
a = []
for i in range(h):
    a.append(inl())
t = [[] for i in range(d)]
for i in range(h):
    for j in range(w):
        x = a[i][j]
        t[x%d].append((x,i,j))
for i in range(d):
    t[i].sort()
#ddprint(t)
acc = [[0]*(len(t[i])+1) for i in range(d)]
for i in range(d):
    for j in range(1,len(t[i])):
        acc[i][j] = acc[i][j-1] + abs(t[i][j][1]-t[i][j-1][1]) \
                                + abs(t[i][j][2]-t[i][j-1][2])
#ddprint(acc)
q = inn()
for qq in range(q):
    l,r = inm()
    i = l%d
    j = l//d
    k = r//d
    if i==0:
        j -= 1
        k -= 1
    print(acc[i][k]-acc[i][j])

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())
B=[list(map(int,input().split())) for _ in range(Q)]
L,R=zip(*B)
C=[[]for i in range(H*W)]
for i in range(H):
  for j in range(W):
    a=A[i][j]
    C[a-1]=((j+1,i+1))
X=[0]*(H*W+1)
for i in range(D):
  x=H*W-D-i
  count=0
  while x>0:
    count+=abs(C[x-1][0]-C[x+D-1][0])+abs(C[x-1][1]-C[x+D-1][1])
    X[x]+=count
    x-=D
for i in range(Q):
  print(X[L[i]]-X[R[i]])

Submission status: Accepted

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

num_point = {}
for i in range(H):
    for j in range(W):
        num_point[grid[i][j]] = (i+1,j+1)

Q = int(input())
lst = [0]*(H*W+1)
LR = []
for _ in range(Q):
    LR.append(list(map(int,input().split())))
    lst[LR[-1][0]] += 1
    lst[LR[-1][1]] -= 1

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

for i in range(1,D+1):
    for j in range(i+D,H*W+1,D):
        sx,sy = num_point[j-D]
        tx,ty = num_point[j]
        ans_lst[j] += ans_lst[j-D]+(abs(tx-sx)+abs(ty-sy))
for L,R in LR:
    print(ans_lst[R]-ans_lst[L])

Submission status: Accepted

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

A = [[0]*W for i in range(H)]
data = [0]*(H*W+1)

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

for i in range(H):
    for j in range(W):
        data[A[i][j]] = [i,j]

Q = int(input())

L = [0] * Q
R = [0] * Q

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

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

for i in range(D):
    x = H*W-D-i
    count = 0
    while x > 0:
        count += abs(data[x][0]-data[x+D][0])+abs(data[x][1]-data[x+D][1])
        X[x] += count
        x -= D

for i in range(Q):
    print(X[L[i]]-X[R[i]])

Submission status: Accepted

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

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [0] * (n + 1)
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d] = D[j] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(D[r] - D[l])        

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    H, W, D = map(int, input().split())
    posX, posY = [0] * (H * W + 1), [0] * (H * W + 1)
    for i in range(H):
        Ai = list(map(int, input().split()))
        for j in range(W):
            posX[Ai[j]] = i
            posY[Ai[j]] = j
    
    d_cum = [0] * (H * W + 1)
    for i in range(D + 1, H * W + 1):
        d_cum[i] = d_cum[i - D] + abs(posX[i] - posX[i - D]) + abs(posY[i] - posY[i - D])
    
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(d_cum[R] - d_cum[L])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

pos = [None] * (H*W)
for i,row in enumerate(A):
    for j,a in enumerate(row):
        pos[a-1] = (i,j)

cums = [0]*D
for (x1,y1),(x2,y2) in zip(pos, pos[D:]):
    d = abs(x1-x2) + abs(y1-y2)
    cums.append(cums[-D] + d)

ans = []
for l,r in LR:
    ans.append(cums[r-1] - cums[l-1])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = [(-1, -1) for i in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for idx in range(1, H*W+1):
        if H*W < idx+D:
            continue
        i, j = dic[idx]
        x, y = dic[idx + D]
        S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()

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())
query = [list(map(int, input().split())) for i in range(q)]

res = [[0] for i in range(d)]
memo = {} 
for i in range(h):
    for j in range(w):
        memo[a[i][j]] = (i, j)
res[0].append(0)
for i in range(1, w * h + 1):
    if i - d not in memo:
        res[i % d].append(0)
    else:
        wi, hi = memo[i]
        wii, hii = memo[i - d]
        diff = abs(wi - wii) + abs(hi - hii)
        res[i % d].append(diff)
        res[i % d][-1] += res[i % d][-2]

for l, r in query:
    mod = l % d
    l = l // d
    r = r // d
    print(res[mod][r + 1] - res[mod][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)]

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

for i in range(h):
    for j in range(w):
        a[i][j] -= 1###
        p[a[i][j]] = (i,j)

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

p2 = [p[i::d] for i in range(d)]
p3 = [[mp(p2[j][i+1],p2[j][i]) for i in range(len(p2[j])-1)] for j in range(d)]
p4 = [[0] for j in range(d)]

for j in range(d):
    sm = 0
    for i in range(len(p3[j])):
        sm += p3[j][i]
        p4[j].append(sm)


q = int(input())

for i in range(q):
    li,ri = map(int,input().split( ))
    li-=1;ri-=1;##a[i]を取得したときに1引いているのでそろえる、これどちらかに統一したほうが
    j = li%d

    print(p4[j][ri//d]-p4[j][li//d])

Submission status: Accepted

Solution code:
##解答を見た 手前でO(H^2W^2) ~O(10^9)くらいのことをしていた
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int,input().split())))

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

for i in range(H):
    for j in range(W):
        pos[A[i][j]][0] = i+1
        pos[A[i][j]][1] = j+1

dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1]))

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):
    print(dist[LR[i][1]-1]-dist[LR[i][0]-1])

Submission status: Accepted

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

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

cst = {}
for i in range(1,D+1):
    cst[i] = 0
for i in range(D+1,H*W+1):
    cst[i] = cst[i-D]+abs(plc[i][0]-plc[i-D][0])+abs(plc[i][1]-plc[i-D][1])


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

Submission status: Accepted

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

dic = {}
for i in range(h):
  line = list(map(int,input().split()))
  for j in range(w):    
    dic[line[j]-1]=(i,j)              

A = [0]*(h*w)

for i in range(h*w-d):
    x,y = dic[i]
    nx,ny = dic[i+d]      
    A[i+d] = A[i] + abs(nx-x) + abs(ny-y)
  
q = int(input())  
for i in range(q):
  l,r = map(int,input().split())
  print(A[r-1] - A[l-1])

Submission status: Accepted

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

dic = {}
for i in range(h):
  line = list(map(int,input().split()))
  for j in range(w):    
    dic[line[j]-1]=(i,j)              

q = int(input())
L = [0]*q
R = [0]*q    
    
for i in range(q):
  L[i],R[i] = map(int,input().split())    
    
A = [0]*(h*w)
i = 0
j = 0
while i < h*w:  
  if A[i]>0:      
    pass
  else:
    j = i+d
    while j < h*w and j-d>=0:
      pos_j = dic[j]
      pos_jd = dic[j-d]
      A[j] = A[j-d] + abs(pos_j[1]-pos_jd[1]) + abs(pos_j[0]-pos_jd[0])    
      j += d        
  i+=1
  
for i in range(q):
  print(A[R[i]-1] - A[L[i]-1])

Submission status: Accepted

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

P = {}

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

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

for a in range(H * W - D):
    i, j = P[a]
    x, y = P[a + D]
    cum[a + D] = cum[a] + abs(x - i) + abs(y - j)

Q = int(input())
ans = []

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

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

Submission status: Accepted

Solution code:
H, W, D, *L = map(int, open(0).read().split())
A = L[:W*H]
Q = L[H*W]
inf = []
for l,r in zip(*[iter(L[H*W+1:])]*2):
  inf += [(l,r)]
dic = {A[i*W+j]:(i,j) for i in range(H) for j in range(W)}
ls = [[] for i in range(D)]
for i in range(D):
  s = i if i!=0 else D
  ls[i].append(0)
  m = s
  n = s
  while True:
    n += D
    if H*W<n:
      n = s
    px, py = dic[m]
    x, y = dic[n]
    ls[i].append(ls[i][-1]+abs(px-x)+abs(py-y))
    m = n
    if m==s:
      break
for l, r in inf:
  i = l%D
  if i==0:
    il = (l-D)//D
    ir = (r-D)//D
  else:
    il = (l-i)//D
    ir = (r-i)//D
  if l<r:
    print(ls[i][ir] - ls[i][il])
  elif l>r:
    print(ls[i][-1]-ls[i][il]+ls[i][ir])
  else:
    print(0)

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = []
N = (H * W)
indices = [None] * (N + 1)
for h in range(H):
    tmp = list(map(int, input().split()))
    A.append(tmp)
    for w in range(W):
        indices[tmp[w]] = (h, w)

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

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())
A = [list(map(int, input().split())) for _ in range(h)]

L = [[0, 0] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        id = A[i][j]
        id -= 1
        L[id][0] = i
        L[id][1] = j

C = [0]*(h*w)
for i in range(h*w):
    ni = i+d
    if ni <= h*w-1:
        C[ni] = C[i]+abs(L[ni][0]-L[i][0])+abs(L[ni][1]-L[i][1])
#print(C)

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

Submission status: Accepted

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

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)]
loc = [None] * (H*W+1)
for y in range(H):
    for x in range(W):
        loc[A[y][x]] = (x, y)
power = [0] * (H*W+1)
for n in range(D+1, H*W+1):
    i, j = loc[n-D]
    x, y = loc[n]
    power[n] = power[n-D] + abs(x-i) + abs(y-j)
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    print(power[R] - power[L])

Submission status: Accepted

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

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

Series=[]
for d in range(1,D+1):
    distance=[0]
    while d+D<=H*W:
        distance.append(distance[-1]+abs(p[d][0]-p[d+D][0])+abs(p[d][1]-p[d+D][1]))
        d+=D
    Series.append(distance)

#print(Series)
Q=int(input())
Ans=[]
for q in range(Q):
    l,r=map(int,input().split())
    if l%D==0:
        Idx=D-1
    else:
        Idx=l%D-1
    Ans.append(Series[Idx][(r-Idx-1)//D]-Series[Idx][(l-Idx-1)//D])

for i in range(Q):
    print(Ans[i])

Submission status: Accepted

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

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

Inds = {x:[] for x in range(1, h*w+1)}
for j in range(h):
    for k in range(w):
        Inds[A[j][k]].append(j)
        Inds[A[j][k]].append(k)

Dist = [-1 for _ in range(h*w+1)]
for i in range(1,h*w+1):
    if i <= d:
        Dist[i] = 0
    else:
        Dist[i] = Dist[i-d] + abs(Inds[i][0]-Inds[i-d][0]) + abs(Inds[i][1]-Inds[i-d][1])

for lr in LR:
    ans = Dist[lr[1]] - Dist[lr[0]]
    print(ans)

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())
px = [0]*(H*W+1)
py = [0]*(H*W+1)
for y in range(H):
    for x in range(W):
        n = A[y][x]
        px[n] = x + 1
        py[n] = y + 1
csum = [0]*(H*W+1)
for i in range(D+1,H*W+1):
    csum[i] = csum[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D])
for q in range(Q):
    L, R = map(int,input().split())
    print(csum[R]-csum[L])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[]
adic={}
hh=1
saidai=0
for _ in range(h):
  temp=(list(map(int,input().split())))
  ww=1
  for item in temp:
    adic[item]=[hh,ww]
    ww+=1
    saidai=max(saidai,item)
  
  hh+=1
  
rdic={}
#print("saidai",saidai)
i=1
    

while i<=d:

  rdic[i]=0
  hoge=i+d
  while hoge<=saidai:
    tempi=adic[hoge-d]
    tempd=adic[hoge]
    rdic[hoge]=rdic[hoge-d]+abs(tempi[0]-tempd[0])+abs(tempi[1]-tempd[1])
    hoge+=d
  i+=1
#print(rdic)

q=int(input())
rl=[]
for _ in range(q):
  rl.append(list(map(int,input().split())))
  
for item in rl:
  print(rdic[item[1]]-rdic[item[0]])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

M = dict()
for y, line in enumerate(A):
    for x, square in enumerate(line):
        M[square] = (x, y)

S = [[] for _ in range(D)]
for i in range(H * W):
    i += 1
    S[i % D].append(M[i])

CS = [[0] for _ in range(D)]
for i in range(D):
    for j in range(1, len(S[i])):
        CS[i].append(CS[i][j-1] + abs(S[i][j-1][0] - S[i][j][0]) + abs(S[i][j-1][1] - S[i][j][1]))

for i in range(Q):
    cumsum = CS[L[i] % D]
    left = (L[i]-1) // D
    right = (R[i]-1) // D
    print(cumsum[right] - cumsum[left])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

input=sys.stdin.readline

H,W,D=map(int,input().split())
A=[[] for i in range(0,H)]
for i in range(0,H):
    A[i]=list(map(int,input().split()))
Q=int(input())
L=[0 for i in range(0,Q)]
R=[0 for i in range(0,Q)]
for i in range(0,Q):
    L[i],R[i]=map(int,input().split())

data=[(0,0) for i in range(0,H*W+1)]
for i in range(0,H):
    for j in range(0,W):
        data[A[i][j]]=(i+1,j+1)
anstable=[[] for i in range(0,D+1)]
for i in range(1,D+1):
    x=(H*W-i)//D
    for j in range(0,x):
        s=data[i+j*D][0]
        t=data[i+j*D][1]
        s2=data[i+(j+1)*D][0]
        t2=data[i+(j+1)*D][1]
        anstable[i].append(abs(s2-s)+abs(t2-t))
    anstable[i]=list(accumulate(anstable[i]))

for i in range(0,Q):
    x=L[i]%D
    if x==0:
        x=D
    if D>=L[i]:
        if R[i]==L[i]:
            print(0)
        else:
            if x!=D:
                print(anstable[x][R[i]//D-1])
            else:
                print(anstable[x][R[i]//D-2])
    else:
        if x!=D:
            print(anstable[x][R[i]//D-1]-anstable[x][L[i]//D-1])
        else:
            print(anstable[x][R[i]//D-2]-anstable[x][L[i]//D-2])

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        pos[A[i][j]] = (i, j)

def L1(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

costs = []

for i in range(H * W + 1):
    costs.append(0 if i <= D else costs[i - D] + L1(pos[i - D], pos[i]))

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
H,W,D = map(int,input().split())
A = []
for h in range(H):
  A = A + list(map(int,input().split()))
for i in range(H*W):
  A[i]=(A[i], i%W, i//W)
A.sort()
Dist=[0]*(H*W)
for i in range(H*W):
  if i>=D:
    Dist[i] = Dist[i-D] + abs(A[i][1]-A[i-D][1]) + abs(A[i][2]-A[i-D][2])
Q = int(input())
for q in range(Q):
  L,R = map(int,input().split())
  ret = Dist[R-1]-Dist[L-1]
  print(ret)

Submission status: Accepted

Solution code:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

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

for l,r in al:
    print(cost[r]-cost[l])