Problem:


Score : 400 points

Problem Statement

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

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

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

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

The i-th test will be conducted as follows:

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

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

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

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

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

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

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

1 \leq Q \leq 10^5

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

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

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

Output

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

Output should be in the order the tests are conducted.

Sample Input 1

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

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

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

Sample Input 2

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

Sample Output 2

0
0

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

Sample Input 3

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

Sample Output 3

0
5
0



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


Sample output:
5

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, D = lr()
A = [lr() for _ in range(H)]
Q = ir()
mul = H*W//D + 1 # Xの横幅
X = np.zeros((D, mul), np.int32)
Y = np.zeros((D, mul), np.int32)

for i in range(H):
    for j in range(W):
        q, r = divmod(A[i][j], D)
        X[r, q] = j
        Y[r, q] = i

magic = np.zeros_like(X)
magic[:, 1:] = (np.abs(np.diff(X, axis=1)) + np.abs(np.diff(Y, axis=1))).cumsum(axis=1)

for i in range(Q):
    l, r = lr()
    q1, r1 = divmod(l, D)
    q2, r2 = divmod(r, D)
    answer = magic[r2, q2] - magic[r1, q1]
    print(answer)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, D = lr()
A = [lr() for _ in range(H)]
Q = ir()
grid = [None] * (H*W + 1) # 1-indexed
for i in range(H):
    for j in range(W):
        grid[A[i][j]] = (i, j)

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

for i in range(Q):
    l, r = lr()
    answer = next_D[r] - next_D[l]
    print(answer)

# 49

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())
lis = [[0,0] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        x = A[i][j]
        lis[x] = [i,j]
li = [[] for _ in range(D)]
su = [[] for _ in range(D)]
for d in range(D):
    li[d] = lis[d::D]
    for i,l in enumerate(li[d]):
        if i == 0:
            su[d].append(0)
            continue
        Power = su[d][i-1]+abs(li[d][i][1]-li[d][i-1][1]) + abs(li[d][i][0]-li[d][i-1][0])
        su[d].append(Power)

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

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w,d = inpm()
    a = inpll(h)
    MAP = [0 for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            MAP[a[i][j]-1] = (i,j)
    cnt = []
    for i in range(h*w-d):
        x = MAP[i]
        y = MAP[i+d]
        cost = abs(x[0]-y[0]) + abs(x[1]-y[1])
        cnt.append(cost)
    ans = [0 for _ in range(h*w)]
    for i in range(h*w-d):
        ans[i+d] += ans[i] + cnt[i]
    q = inp()
    for _ in range(q):
        l,r = inpm()
        print(ans[r-1]-ans[l-1])
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
A=[[0]*w for i in range(h)]
B=[0]*(w*h)
C=[0]*(w*h)
for i in range(h):
  A[i]=list(map(int,input().split()))
  for j in range(w):
    B[A[i][j]-1]=i
    C[A[i][j]-1]=j
D=[0]*(h*w)
for i in range(d,w*h):
  D[i]=D[i-d]+abs(B[i-d]-B[i])+abs(C[i-d]-C[i])
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  print(D[b-1]-D[a-1])

Submission status: Accepted

Solution code:
H,W,D=map(int, input().split())
A=[()]*(H*W+1)
for i in range(H):
    for j,a in enumerate(map(int, input().split())):
        A[a]=(i,j)
Q=int(input())
LR=[tuple(map(int, input().split())) for _ in range(Q)]

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

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

for L,R in LR:
    print(dist[R]-dist[L])

Submission status: Accepted

Solution code:
# 累積話の考え方を使う
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
# print(status)

# 目的地は必ずDだけ小さいマスからしか移動してこない
cumulative_sum = [0] * (H*W+1)
for i in range(H*W+1):
    if i <= D:
        cumulative_sum[i] = 0
        continue
    else:
        cumulative_sum[i] = cumulative_sum[i-D] + abs(status[i][0] - status[i-D][0]) + abs(status[i][1] - status[i-D][1])

for s, t in query:
    print(cumulative_sum[t] - cumulative_sum[s])

Submission status: Accepted

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

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

for i in range(h * w-d):
    num[i%d][i//d+1] = num[i%d][i//d]+abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(num[now%d-1][(goal-now%d)//d-1]-num[now%d-1][(now-now%d)//d-1])
    else:
        print(num[now%d-1][(goal-now%d)//d]-num[now%d-1][(now-now%d)//d])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
n = h*w
L = [0]*(n+1)
def dis(p, q):
  return abs(p[0]-q[0]) + abs(p[1]-q[1])
for i in range(h):
  for j in range(w):
    t = A[i][j]
    L[t] = (i, j)
K = [0]*(n+1)
for i in range(1, n-d+1):
  K[i+d] = dis(L[i+d], L[i])
  K[i+d] += K[i]
q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  print(K[r] - K[l])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [None] * (H*W)
C = [0] * (H*W)
for h, aa in enumerate(A):
    for w, a in enumerate(aa):
        B[a-1] = h, w
for i in range(H*W-D):
    C[i+D] = C[i] + abs(B[i][0]-B[i+D][0]) + abs(B[i][1]-B[i+D][1])
for _ in range(int(input())):
    L, R = map(int, input().split())
    print(C[R-1]-C[L-1])

Submission status: Accepted

Solution code:
H,W,D = list(map(int,input().split()))
mat = [0 for i in range(H*W)]
A = []
for h in range(H):
    a = list(map(int,input().split()))
    A.append(a)
    for w in range(W):
        mat[a[w]-1] = [h,w]
Q = int(input())
LR = [list(map(int,input().split())) for i in range(Q)]
dlist = [0 for i in range(H*W)]
for i in range(H*W):
    if i+1 > D:
        dlist[i] = abs(mat[i][0]-mat[i-D][0]) + abs(mat[i][1]-mat[i-D][1]) +dlist[i-D]
for l,r in LR:
    print(dlist[r-1]-dlist[l-1])

Submission status: Accepted

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


h, w, d = map(int, input().split())
num_to_x = [0] * (h*w+1)
num_to_y = [0] * (h*w+1)

for y in range(h):
    line = list(map(int, input().split()))
    for x, num in enumerate(line):
        num_to_x[num] = x
        num_to_y[num] = y

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

for start in range(1, d+1):
    cost = 0
    num = start
    sx, sy = num_to_x[num], num_to_y[num]
    while num <= h*w:
        nx, ny = num_to_x[num], num_to_y[num]
        cost += abs(nx-sx) + abs(ny-sy)
        costs[num] = cost
        sx, sy = nx, ny
        num += d

q = int(input())

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

Submission status: Accepted

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

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

num_to_xy = [[0, 0] for i in range(h*w + 1)]

for y in range(h):
    for x in range(w):
        num = A[y][x]
        num_to_xy[num] = [x, y]

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

for start in range(1, d+1):
    cost = 0
    num = start
    sx, sy = num_to_xy[num]
    while num <= h*w:
        nx, ny = num_to_xy[num]
        cost += abs(nx-sx) + abs(ny-sy)
        costs[num] = cost
        sx, sy = nx, ny
        num += d

q = int(input())

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

Submission status: Accepted

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

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

num_to_xy = [[0, 0] for i in range(h*w + 1)]

for y in range(h):
    for x in range(w):
        num = A[y][x]
        num_to_xy[num] = [x, y]

costs = [[] for i in range(d+1)]
for mod in range(1, d+1):
    num = mod
    sx, sy = num_to_xy[num]
    cost = 0
    while num <= h*w:
        nx, ny = num_to_xy[num]
        cost += abs(nx-sx) + abs(ny-sy)
        costs[mod].append(cost)
        num += d
        sx, sy = nx, ny

q = int(input())

for _ in range(q):
    l, r = map(int, input().split())
    mod = l % d
    if mod == 0:
        mod = d
    idx = (l-mod) // d
    step = (r-l) // d

    res = costs[mod][idx+step] - costs[mod][idx]
    print(res)

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

m=[[None]*(H*W//D+1) for _ in range(D+1)]
#print(m)
for h in range(H):
    for w in range(W):
        amari=A[h][w]%D
        shou=A[h][w]//D
        if amari==0:
            amari=D
            shou-=1
        m[amari][shou]=[h,w]

"""for i in m:
    print(i)
"""
mrui=[[0]for _ in range(D+1)]
for i in range(D+1):
    for j in range(1,H*W//D+1):
        if m[i][j]!=None and m[i][j-1]!=None:
            x=abs(m[i][j][0]-m[i][j-1][0])
            y=abs(m[i][j][1]-m[i][j-1][1])
            mrui[i].append(x+y)
for i in mrui:
    for j in range(1,len(i)):
        i[j]+=i[j-1]
#print(mrui)

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ramari=R%D
    rshou=R//D
    if ramari==0:
        ramari=D
        rshou-=1
    lamari=L%D
    lshou=L//D
    if lamari==0:
        lamari=D
        lshou-=1
    print(mrui[ramari][rshou]-mrui[lamari][lshou])

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:
import sys
input = sys.stdin.buffer.readline

def main():
    H,W,D = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    Q = int(input())
    test = [list(map(int,input().split())) for _ in range(Q)]
    
    at = [None for _ in range(H*W)]
    for x in range(H):
        for y in range(W):
            at[A[x][y]-1] = (x,y)
            
    def move(x,y):
        dx = abs(at[y][0]-at[x][0])
        dy = abs(at[y][1]-at[x][1])
        return dx + dy
            
    cost = [[0 for _ in range(-(-H*W//D))] for _ in range(D)]
    for i in range(D):
        do = -(-(H*W-i)//D)
        for j in range(do-1):
            cost[i][j+1] = cost[i][j] + move(D*j+i,D*(j+1)+i)
            
    for i in range(Q):
        start,goal = test[i]
        v = start % D - 1
        u = -(-start // D) - 1
        w = -(-goal // D) - 1
        print(cost[v][w]-cost[v][u])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [None]*(H*W+1)
for i in range(H):
    a = [int(i) for i in input().split()]
    for j, v in enumerate(a):
        A[v] = (i+1, j+1)

Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

x = [-1]*H*W
y = [-1]*H*W

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

X = [0]*H*W
Y = [0]*H*W
# 累積和行列化
for k in range(D, H*W):
    X[k] = X[k-D]+abs(x[k]-x[k-D])
    Y[k] = Y[k-D]+abs(y[k]-y[k-D])

for L, R in query:
    L -= 1  # 0-indexed
    R -= 1  # 0-indexed
    print(X[R]-X[L]+Y[R]-Y[L])

Submission status: Accepted

Solution code:
import sys

h, w, d = map(int, sys.stdin.readline().split())
a = [[int(x) for x in sys.stdin.readline().split()] for _ in range(h)]
q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2) 

def main():
    place = [None] * (h * w + 1)
    for i in range(h):
        for j in range(w):
            place[a[i][j]] = (i, j)
    
    cost = [None] * (h * w + 1)
    for x in range(1, 1+d):
        cost[x] = 0
        i, j = place[x]
        while x + d <= h * w:
            nex = x + d
            nex_i, nex_j = place[nex]
            cost[nex] = cost[x] + abs(nex_i - i) + abs(nex_j - j)
            x = nex
            i, j = nex_i, nex_j

    for l, r in lr:
        yield cost[r] - cost[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

h, w, d = map(int, sys.stdin.readline().split())
a = [[int(x) for x in sys.stdin.readline().split()] for _ in range(h)]
q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2) 

def main():
    place = [None] * (h * w + 1)
    for i in range(h):
        for j in range(w):
            place[a[i][j]] = (i, j)
    
    cost = [0] * (h * w + 1)
    cost[0] = None
    for x in range(1, 1+d):
        i, j = place[x]
        while x + d <= h * w:
            nex = x + d
            nex_i, nex_j = place[nex]
            cost[nex] = cost[x] + abs(nex_i - i) + abs(nex_j - j)
            x = nex
            i, j = nex_i, nex_j

    for l, r in lr:
        yield cost[r] - cost[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

h, w, d = map(int, sys.stdin.readline().split())
a = [[int(x) for x in sys.stdin.readline().split()] for _ in range(h)]
q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2) 

def main():
    place = [None] * (h * w + 1)
    for i in range(h):
        for j in range(w):
            place[a[i][j]] = (i, j)
    
    cost = [0] * (h * w + 1)
    cost[0] = None
    for x in range(1, 1+d):
        while x + d <= h * w:
            nex = x + d
            i, j = place[x]
            k, l = place[nex]
            cost[nex] = cost[x] + abs(j - l) + abs(i - k)
            x = nex

    for l, r in lr:
        yield cost[r] - cost[l]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
Data = [0] * (H*W)
for h in range(H):
    tmp = list(map(int,input().split()))
    for w in range(W):
        s = tmp[w]
        Data[s-1] = [h,w]

Q = int(input())
Questions = []
for _ in range(Q):
    Questions.append(list(map(int,input().split())))

Acc = [0] * (H*W+1)
Acc[0] = 0
for i in range(1,H*W+1):
    if i < D:
        Acc[i] = 0
    else:
        plus  = abs(Data[i-1][0]-Data[i-D-1][0])
        plus += abs(Data[i-1][1]-Data[i-D-1][1])
        Acc[i] = Acc[i-D] + plus

#for i in range(H*W):
#    print(i+1,Data[i])
#print(Acc)

for l,r in Questions:
    print(Acc[r]-Acc[l])

Submission status: Accepted

Solution code:
H, W , D = map(int, input().split())
fields = []
X = []

# print(pairs)
def calc_dist(a,b):
    return abs(a//W-b//W) + abs(a%W-b%W)
for i in range(H):
    # fields.append(list(map(int, input().split())))
    X.extend(list(map(int, input().split())))
pairs = [(x-1,i) for i,x in enumerate(X)]
pairs.sort()
numbers = [p[1] for p in pairs]
# D個ずつの累積和を取る
# print(numbers)
from itertools import accumulate
from collections import defaultdict


d = defaultdict(list)
for i in range(D):
    prev = numbers[i]
    acc = 0
    d[i] = [0]
    for num in numbers[i+D:len(numbers):D]:
        acc += calc_dist(prev,num)
        d[i].append(acc)
        prev = num
# print(d)    
    


Q = int(input())
for i in range(Q):
    L1,R1 = map(int, input().split())
    L1 -= 1
    R1 -= 1
    acc = d[L1%D]
    # print("acc",acc)
    print(acc[R1//D]-acc[L1//D])

Submission status: Accepted

Solution code:
def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    E = [0] * (H * W)
    for i in reversed(range(H * W - D)):
            E[i] = E[i + D] + C[i]
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(E[l - 1] - E[r - 1])
        
main()

Submission status: Accepted

Solution code:
import numpy as np
h, w, d = map(int, input().split())
X = np.zeros(h*w, dtype=int)
Y = np.zeros(h*w, dtype=int)
score = np.zeros(h*w, dtype=int)
for x in range(h):
    inp = tuple(map(int, input().split()))
    for y in range(w):
        i = int(inp[y]) - 1
        X[i] = x
        Y[i] = y

score[d:] += np.abs(X[d:] - X[:-d]) + np.abs(Y[d:] - Y[:-d])
for i in range(len(score) - d):
    score[i+d] += score[i]

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

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w,d = inpl()
a = [inpl() for i in range(h)]
de = defaultdict(int)
for i in range(h):
    for j in range(w):
        de[a[i][j]] = (i,j)
li = dict()
for i in range(d):
    c = 0
    tmp = 0
    while True:
        if de[i+d*c] == 0:
            c += 1
            continue
        tmp = de[i+d*c]
        break
    li[i+d*c] = 0
    while True:
        c += 1
        if de[i+d*c] == 0:
            break
        now = de[i+d*c]
        kyori = abs(now[0]-tmp[0]) + abs(now[1]-tmp[1])
        li[i+d*c] = li[i+d*(c-1)] + kyori
        tmp = now
# print(li)
q = inp()
lr = [inpl() for i in range(q)]
for l,r in lr:
    print(li[r] - li[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())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

reach = [0] * (w * h)
for i in range(h):
    for j in range(w):
        reach[a[i][j] - 1] = [i, j]
#print(reach)

count = [0] * (w * h)
for i in range((w * h)):
    if i - d < 0 : 
        pass
    else:
        count[i] = count[i - d] + (abs(reach[i][0] - reach[i - d][0]) + abs(reach[i][1] - reach[i - d][1]))
#print(count)

for i in range(q):
    print(count[r[i] - 1] - count[l[i] - 1])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W,D=MI()
    A=LLIN(H)
    
    def get_cost(fr:tuple, to:tuple):
        return abs(fr[0]-to[0]) + abs(fr[1]-to[1])

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

    cumsum = [0]*(H*W+1+D)
    for x in range(1,H*W):
        if x+D not in cord_of_x:
            break
        cost = get_cost(cord_of_x[x], cord_of_x[x+D])
        cumsum[x+D]+=cumsum[x]+cost


    Q=I()
    LR=LLIN(Q)
    for l,r in LR:
        d = l%D
        print(cumsum[r]-cumsum[l])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

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

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

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

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])

Submission status: Accepted

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

def find_element(k):
    global h,w,a
    for i in range(h):
        for j in range(w):
            if a[i][j]==k:
                return (i,j)

def make_distance(S,T):
    return abs(S[0]-T[0])+abs(S[1]-T[1])

x1=[]
x2=[]
for i in range(1,d+1):
    l=(h*w-i)//d
    x1.append([0]*(l+1))
    x2.append([[0,0]for i in range(l+1)])

for i in range(h):
    for j in range(w):
        p=a[i][j]%d
        if p==0:
            p=d-1
        else:
            p-=1
        l=(a[i][j]-(p+1))//d
        x2[p][l]=[i,j]


for i in range(1,d+1):
    l=len(x1[i-1])
    for j in range(l-1):
        x1[i-1][j+1]=x1[i-1][j]+make_distance(x2[i-1][j],x2[i-1][j+1])

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    p=l%d
    if p==0:
        v1=l//d-1
        v2=r//d-1
        print(x1[d-1][v2]-x1[d-1][v1])
    else:
        v1=l//d
        v2=r//d
        print(x1[p-1][v2]-x1[p-1][v1])
#print(x)

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
X, Y, ans = [-1] * H * W, [-1] * H * W, [0] * H * W

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

for d in range(D):
    while d + D < H * W:
        ans[d + D] = ans[d] + abs(X[d] - X[d + D]) + abs(Y[d] - Y[d + D])
        d += D

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

Submission status: Accepted

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

aToHW = {}
for h in range(H):
    for w, a in enumerate(A[h]):
        aToHW[a] = (h, w)

cnt = [-1] * (H * W + 1)
for start in range(1, H * W + 1)[:: -1]:
    c = 0
    for now in range(start, H * W + 1, D):
        if now + D > H * W:
            break
        if cnt[now] >= 0:
            c += cnt[now]
            break

        nH, nW = aToHW[now]
        tH, tW = aToHW[now + D]
        c += abs(nH - tH) + abs(nW - tW)
    cnt[start] = c

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
H,W,D = map(int,input().split())
A = [list(map(int,readline().split())) for i in range(H)]
Q=int(input())
Qls = [list(map(int,readline().split())) for i in range(Q)]
X = []
for i in range(H):
    for j in range(W):
        X.append([A[i][j],i,j])
X.sort()
wa = [[0 for i in range(H*W//D+1)] for j in range(D+1)]
for i in range(1,H*W+1):
    qt = i//D
    mod = i%D
    if qt >= 1:
        wa[mod][qt]=wa[mod][qt-1]+abs(X[i-1][1]-X[i-1-D][1])+abs(X[i-1][2]-X[i-1-D][2])
for i in range(Q):
    qti = Qls[i][0]//D
    mod = Qls[i][0]%D
    qtf = Qls[i][1]//D
    print(wa[mod][qtf]-wa[mod][qti])

Submission status: Accepted

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

def main():
    H, W, D = map(int, input().split())
    A = list(list(map(int, input().split())) for _ in range(H))
    Q = int(input())
    B = [(0,0)] * (H * W + 5)
    for h in range(H):
        for w in range(W): 
            B[A[h][w]] = (h+1, w+1)


    C = [0] * (H * W + 5)
    for i in range(H * W + 1):
        if i // D == 0:
            continue
        tmp = abs(B[i][0] - B[i-D][0]) + abs(B[i][1] - B[i-D][1]) 
        C[i] = tmp + C[i - D]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Practical Skill Test

import sys

H, W, D = map(int, sys.stdin.buffer.readline().split())
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(H)]

place = [-1] * (H*W + 1)
for row in range(H):
    for col in range(W):
        place[A[row][col]] = (row, col)

cum_cost = [[0] for _ in range(D+1)]
for i in range(1, D+1):
    x = i
    y = x + D
    while y <= H*W:
        cum_cost[i].append(cum_cost[i][-1] + abs(place[x][0] - place[y][0]) + abs(place[x][1] - place[y][1]))
        x += D
        y += D

Q = int(sys.stdin.buffer.readline())

for _ in range(Q):
    L, R = map(int, sys.stdin.buffer.readline().split())
    ans = 0
    tmp = L % D
    if tmp == 0:
        print(cum_cost[-1][R // D - 1] - cum_cost[-1][L // D - 1])
    else:
        print(cum_cost[tmp][R // D] - cum_cost[tmp][L // D])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
e={}
for i in range(1,h+1):
    a=list(map(int,input().split()))
    for j in range(w):
        e[a[j]]=(i,j+1)
q=int(input())
ans=[0]*(h*w+1)
for i in range(d+1,h*w+1):
    x,y=e[i]
    z,m=e[i-d]
    ans[i]=abs(x-z)+abs(y-m)+ans[i-d]
    
for i in range(q):
    l,r=map(int,input().split())
    print(ans[r]-ans[l])

Submission status: Accepted

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

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

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

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