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:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
As = [(0, 0, 0)]
for i in range(H):
    for j in range(W):
        As.append((A[i][j], i+1, j+1))
Q = int(input())
Qs = [list(map(int, input().split())) for _ in range(Q)]
As.sort()
dp = [0] * (H*W+1)
for i in range(1, H*W+1- D):
    a1, j, k = As[i]
    a2, x, y = As[i+D]
    dp[i+D] = dp[i] + abs(x-j) + abs(y-k)
    
for l, r in Qs:
    print(dp[r] -dp[l])

Submission status: Accepted

Solution code:
H,W,D = [ int(it) for it in input().split() ]
li = [ [ int(it)-1 for it in input().split() ] for i in range(H) ]

pos = [0]*(H*W)
for h in range(H):
  for w in range(W):
    pos[li[h][w]]=(h,w)
    
di = [0]*(H*W)
for i in range(H*W):
  if (D<=i):
    sx,sy=pos[i-D]
    gx,gy=pos[i]
    di[i]=di[i-D]+abs(sx-gx)+abs(sy-gy)
    
Q = int(input())
for i in range(Q):
  l,q=[ int(it)-1 for it in input().split() ]
  print ( di[q]-di[l] )

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])

Submission status: Accepted

Solution code:
# ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

rui={}
for i in range(d):
    T=[0]
    for j in range(1,h*w+1-i-d,d):
        T.append(abs(Al[j+i][0]-Al[j+d+i][0])+abs(Al[j+i][1]-Al[j+d+i][1]))
    for j in range(len(T)-1):
        T[j+1]+=T[j]
    rui[(i+1)%d]=T
q=I()
for w in range(q):
    l,r=IL()
    idx=l%d
    if idx==0:
        li=l//d-1
        ri=r//d-1
    else:
        li=l//d
        ri=r//d
    print(rui[idx][ri]-rui[idx][li])

Submission status: Accepted

Solution code:
def dist(ai:int, bi:int, aj:int, bj:int):
    return abs(ai-aj)+abs(bi-bj)

h, w, d = map(int, input().split())
p = {}
for i in range(h):
    tmpstr = input().split()
    for j in range(w):
        tmpchar = int(tmpstr[j])
        p[tmpchar] = (i, j)
dsum = [0]*d
for i in range(d, h*w):
    curl, curr = p[i+1]
    prel, prer = p[i-d+1]
    diff = dist(curl, curr, prel, prer)
    tmpd = dsum[i-d]+diff
    dsum.append(tmpd)

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(dsum[r-1]-dsum[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())
LR=[list(map(int,input().split())) for i in range(Q)]
pos=[(-1,-1) for i in range(H*W+1)]
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=(h,w)
cost=[0]*(H*W+1)
for i in range(1+D,H*W+1):
    cost[i]=cost[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
for q in range(Q):
    print(cost[LR[q][1]]-cost[LR[q][0]])

Submission status: Accepted

Solution code:
h,w,d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
dic = [0]*(h*w)
for i in range(h):
  for j in range(w):
    dic[a[i][j]-1] = (i,j)
sup = [0]*(h*w)
for x in range(d,h*w):
  sup[x] = sup[x-d] + abs(dic[x][0]-dic[x-d][0]) + abs(dic[x][1]-dic[x-d][1])
q = int(input())
for _ in range(q):
  l,r = map(int, input().split())
  print(sup[r-1]-sup[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())
pos=[0]*(h*w)
cost=[[0]*(h*w//d+1) for i in range(d)]

for i in range(h):
    for j in range(w):
        pos[a[i][j]-1]=(i, j)
for i in range(d):
    j=0
    while (j+1)*d+i<w*h:
        p0=pos[j*d+i]
        p1=pos[(j+1)*d+i]
        cost[i][j]=abs(p0[0]-p1[0])+abs(p0[1]-p1[1])
        j+=1

sum_cost=[[0]*(h*w//d+2) for i in range(d)]
for i in range(d):
    for j in range(1, h*w//d+2):
        sum_cost[i][j]=sum_cost[i][j-1]+cost[i][j-1]

for i in range(q):
    l, r = map(int, input().split())
    li=(l-1)//d
    ri=(r-1)//d
    amari=(l-1)%d
    print(sum_cost[amari][ri]-sum_cost[amari][li])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l={}
for i in range(h):
  l1=list(map(int,input().split()))
  for j in l1:
    l[j]=[l1.index(j)+1,i+1]
li=[]
for i in range(1,d+1):
  l11=[]
  c=0
  x=l[i][0]
  y=l[i][1]
  while i<=h*w:
    c+=abs(x-l[i][0])+abs(y-l[i][1])
    l11.append(c)
    x=l[i][0]
    y=l[i][1]
    i+=d
  li.append(l11)
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  r=a%d
  if r==0:
    print(li[d-1][b//d-1]-li[d-1][a//d-1])
  else:
    print(li[r-1][b//d]-li[r-1][a//d])

Submission status: Accepted

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

# h_pos[a]: a がある位置の h
# w_pos[a]: a がある位置の w
h_pos = np.zeros(H * W + 1)
w_pos = np.zeros(H * W + 1)
for h in range(H):
    for w in range(W):
        h_pos[A[h][w]] = h
        w_pos[A[h][w]] = w

dp = np.zeros(H * W + 1, dtype=int)
for i in range(1, H * W + 1):
    if i - D >= 0:
        dp[i] = dp[i - D] + abs(h_pos[i - D] - h_pos[i]) + abs(w_pos[i - D] - w_pos[i])

for l, r in zip(L, R):
    print(dp[r] - dp[l])

Submission status: Accepted

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

remmap = {}
for v, i, j in sorted(sum([[(v, i, j) for j, v in enumerate(map(int, input().split()), start=1)] for i in range(1, H+1)], [])):
    rem = v%D
    if not rem in remmap:
        remmap[rem] = [(v,i,j)]
    else:
        remmap[rem].append((v,i,j))

accmap = {}
# print(remmap)
for rem, lis in remmap.items():
    for i in range(len(lis)):
        if i == 0:
            accmap[rem] = (lis[0][0], [0])
        else:
            fv, l = accmap[rem]
            l.append(l[i-1] + abs(lis[i][1]-lis[i-1][1])+abs(lis[i][2]-lis[i-1][2]))

# print(accmap)
for i in range(int(input())):
    L,R=map(int,input().split())
    rem=L%D
    fv, lis = accmap[rem]
    print(lis[(R-fv)//D]-lis[(L-fv)//D])

Submission status: Accepted

Solution code:
#1<=Dまでの数全てにおいて、+Dしたときの経路コストを求める
#これは１つの数につき１度しか走らないのでO(N)=O(90000)

H,W,D=map(int,input().split())
A=[-1 for j in range(H*W)]
for j in range(H):
    inp=map(int,input().split())
    for r,i in enumerate(inp):
        
        A[i-1]=(j,r) #1は0

cost=[-1 for j in range(H*W)]    
for j in range(0,D):
    i=j
    cost[i]=0
    while True:
        i+=D
        if(i>=H*W):
            break

        cost[i]=cost[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[i-D][1])


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

Submission status: Accepted

Solution code:
#D問題
import math
H,W,D=map(int,input().split())
A=[]
amap=[[-1,-1] for i in range(H*W+D)]
for i in range(H):
    a=list(map(int,input().split()))
    for j in range(W):
        amap[a[j]]=[i,j]
    A.append(a)
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]
syo=int(H*W/D)
dp=[[0 for i in range(syo+1)] for j in range(D)] #dp[modD][/D]=(modDまでの距離)
for i in range(1,syo+1):
    j=0
    if i == syo:
        d=H*W%D
        for j in range(d):
            dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-D][0])+abs(amap[i*D+j][1]-amap[i*D+j-D][1])  
    for j in range(D):
        dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-D][0])+abs(amap[i*D+j][1]-amap[i*D+j-D][1])
for i in range(Q):
    L=LR[i][0]
    R=LR[i][1]
    mod=L%D
    l=int(L/D)
    r=int(R/D)
    print(dp[mod][r]-dp[mod][l])

Submission status: Accepted

Solution code:
from math import ceil
H,W,D=map(int,input().split())
A=[[0]*(int(ceil(H*W/D))) for i in range(D)]
for i in range(H):
    Ai=list(map(int,input().split()))
    for j in range(W):
        A[(Ai[j]-1)%D][(Ai[j]-1)//D]=(i,j)
B=[[0]*(int(ceil(H*W/D))+1) for i in range(D)]
for j in range(D):
    for i in range(len(A[j])):
        if  type(A[j][i])!=type((0,0)):
            #B[j][i+1]=B[j][i]
            break
        if i==0:
            B[j][i+1]=A[j][i][0]+A[j][i][1]
            continue
        B[j][i+1]=B[j][i]+abs(A[j][i-1][0]-A[j][i][0])+abs(A[j][i-1][1]-A[j][i][1])
Q=int(input())
for _ in range(Q):
    L,R=map(int,input().split())
    L,R=L-1,R-1
    print(B[R%D][R//D+1]-B[L%D][L//D+1])

Submission status: Accepted

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

mp = [0]*(H*W)
x = [-1]*(H*W)
y = [-1]*(H*W)

for i, line in enumerate(A):
    for j, a in enumerate(line):
        x[a] = i
        y[a] = j

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

for l, r in query:
    print(mp[r]-mp[l])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

pos = [-1]*(H*W)

for i, line in enumerate(A):
    for j, a in enumerate(line):
        pos[a] = (i,j)

mp_list = [[0] for _ in range(D)]

for r in range(D):
    res = []
    for k in range(H*W):
        if r + k*D <= H*W - 1:
            res.append(pos[r+k*D])
        else:
            break
    for l in range(len(res)-1):
        i, j = res[l]
        ni, nj = res[l+1]
        mp = abs(ni-i) + abs(nj-j)
        mp_list[r].append(mp)

for i in range(D):
    mp_list[i] = list(accumulate(mp_list[i]))

for left, right in query:
    r = left % D
    q1 = (left-r) // D
    q2 = (right-r) // D
    ans = mp_list[r][q2] - mp_list[r][q1]
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    pos = [None for i in range(H * W)]
    for h in range(H):
        for w in range(W):
            pos[A[h][w]] = (h, w)
    
    mp = [0 for i in range(H * W)]
    for d in range(D):
        for i in range(d, H*W-D, D):
            hp, wp = pos[i]
            hn, wn = pos[i+D]
            mp[i+D] = mp[i] + abs(hn-hp) + abs(wn-wp)

    for q in range(Q):
        print(mp[R[q]] - mp[L[q]])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [ [ int(next(tokens))-1 for _ in range(W) ] for _ in range(H) ]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]" 
    R = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        L[i] = int(next(tokens))-1
        R[i] = int(next(tokens))-1
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
cell = [[0,0] for _ in range(h*w+1)]
for y in range(h):
    for x,value  in zip(range(1,w+1),input().split()):
        x = int(x)
        cell[int(value)][0] = x
        cell[int(value)][1] = y
        
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
S = [0]*(h*w+1)

for i in range(1,d+1):
    temp = cell[i]
    S[i] = cell[i][0]+cell[i][1]
    for j in range(i+d,h*w+1,d):
        S[j] = S[j-d]+abs(cell[j][0]-temp[0])+abs(cell[j][1]-temp[1])
        temp = cell[j]
Ans = []
for l,r in LR:
    Ans.append(S[r] -S[l])
print(*Ans,sep = "\n")

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

y=[[-1,-1] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        y[a[i][j]]=[i,j]

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

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

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

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

for i in range(H):
    for j in range(W):
        y[a[i][j]]=[i,j]

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

for i in range(D):
    j=H*W-i-D
    while j>0:
        tmp1,tmp2=abs(y[j][0]-y[j+D][0]),abs(y[j][1]-y[j+D][1])
        x[i].append(x[i][-1]+tmp1+tmp2)
        j-=D

for q in range(Q):
    L,R=map(int,input().split())
    i=(H*W-R)%D
    l=(H*W-i-R)//D
    r=(H*W-i-L)//D
    print(x[i][r]-x[i][l])

Submission status: Accepted

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

n_xy = [0]*(H*W)
for i,row in enumerate(A):
    for j,a in enumerate(row):
        n_xy[a-1] = [i,j]
S = [0]*(H*W)
for i in range(D,H*W):
    S[i] = S[i-D] + abs(n_xy[i][0] - n_xy[i-D][0]) + abs(n_xy[i][1] - n_xy[i-D][1])
for L,R in LR:
    print(S[R-1]-S[L-1])

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

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij-1] = (r, c)
    

dist = [[] for _ in range(d)]
for i in range(h*w):
    if i // d == 0:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li_()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(H):
    j = 0
    for a in input().split():
        X[int(a)] = (i, j)
        j += 1

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

for i in range(1, H*W+1):
    if i+D <= H*W:
        S[i+D] += S[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])


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

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)
Q=int(input())
'''
li = [0]*(H*W+2)
for i in range(1,D+1):
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])
'''

li ={}
for i in range(H):
    for j in range(W):
        li[f[i][j]]=[i+1,j+1]
res=[0]*(H*W+1)
for i in range(1,D+1):
    for j in range(i+D,W*H+1,D):
        #print("j",j)
        #print(li[j][0],li[j][1])
        res[j] = res[j-D] +abs(li[j-D][0]-li[j][0]) + abs(li[j-D][1]-li[j][1])
#print(res)
for i in range(Q):
    L,R = na()
    print(res[R]-res[L])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
k=[[[]]*((h*w)//d+1 if (h*w)%d>i else (h*w)//d )for i in range(d)]
r=[[0]*((h*w)//d+1 if (h*w)%d>i else (h*w)//d )for i in range(d)]
for i in range(h):
    s=list(map(int,input().split()))
    for j in range(w):
        p=s[j]
        k[d-1 if p%d==0 else p%d-1][(p-1)//d]=[i,j]
for i in range(d):
    for s in range(1,len(k[i])):
        r[i][s]=r[i][s-1]+abs(k[i][s][1]-k[i][s-1][1])+abs(k[i][s][0]-k[i][s-1][0])
for i in range(int(input())):
    s,t=map(int,input().split())
    print(r[d-1 if t%d==0 else t%d-1][(t-1)//d]-r[d-1 if s%d==0 else s%d-1][(s-1)//d])

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 = [list(map(int,input().split())) for _ in range(q)]
dic = {}
for i in range(len(a)):
    for j in range(len(a[i])):
        dic[a[i][j]] = (i,j)
sum = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    sum[i] = sum[i-d]+abs(dic[i][0]-dic[i-d][0])+abs(dic[i][1]-dic[i-d][1])
for l_ in l:
    print(sum[l_[1]]-sum[l_[0]])

Submission status: Accepted

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


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


Cost = [0] * (H * W + 1)
for d in range(D + 1, H * W + 1):
    h, w = Position[d]
    prev_h, prev_w = Position[d - D]
    Cost[d] = abs(h - prev_h) + abs(w - prev_w) + Cost[d - D]


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 = [int(i) for i in input().split(" ")]
a = [[] for i in range(0, h)]

for i in range(0, h):
    a[i] = [int(j) for j in input().split(" ")]

q = int(input())
l = []
r = []

for i in range(0, q):
    li, ri = [int(i) for i in input().split(" ")]
    l.append(li)
    r.append(ri)

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

for i in range(0, h):
    for j in range(0, w):
        cor[a[i][j]] = [i, j]

def mp(p, q):
    global cor
    return abs(cor[p][0] - cor[q][0]) +  abs(cor[p][1] - cor[q][1])

for m in range(1, d + 1):
    x = m + d
    while x <= h * w:
        s[x] = s[x - d] + mp(x, x - d)
        x += d

for i in range(0, q):
    print(s[r[i]] - s[l[i]])

Submission status: Accepted

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

size = h * w
dist = [[0] * ((size)//d + 1) for _ in range(d)]
ilist = [0] * (size+1)
jlist = [0] * (size+1)

for i in range(h):
  for j in range(w):
    ilist[a[i][j]] = i
    jlist[a[i][j]] = j

def get_dist(x, y):
  distance = abs(ilist[x] - ilist[y]) + abs(jlist[x] - jlist[y])
  return distance

for i in range(d):
  for j in range((size)//d + 1):
    if (j-1)*d+i <= 0 or j*d + i > size:
      continue
    dist[i][j] = dist[i][j-1] + get_dist(j*d+i, (j-1)*d+i)

for l, r in lr:
  print(dist[r%d][r//d] - dist[l%d][l//d])

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
 

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

Q = int(input())
csum = [0] * (H*W+1) # cumA[i] := i%D -> i に向かう累積和
for i in range(D+1,H*W+1):
  csum[i] = csum[i-D] + abs(An[i][0]-An[i-D][0]) + abs(An[i][1]-An[i-D][1])


ans = [0] * Q
for i in range(Q):
  l,r = map(int, input().split())
  ans[i] = csum[r] - csum[l]

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
x=[0 for i in range(H*W+1)]
y=[0 for i in range(H*W+1)]
memo=[None for i in range(H*W+1)]
for j in range(H):
    A=list(map(int,input().split()))
    for i,a in enumerate(A):
        x[a]=i
        y[a]=j
Q=int(input())
ans=[]
for i in range(Q):
    L,R=map(int,input().split())
    if memo[D] is None:
        memo[D] = [0]*(D+1)
        for i in range(D+1,H*W+1):
            memo[D].append(memo[D][i-D]+abs(x[i]-x[i-D])+abs(y[i]-y[i-D]))
    ans.append(memo[D][R]-memo[D][L])
for a in ans:
    print(a)

Submission status: Accepted

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

data = []

for i in range(h):
    l = list(map(int,input().split()))
    for j in range(w):
        data.append((l[j],i+1,j+1))

data.sort(key = lambda x:x[0])
#print(data)
dis = [0]*(h*w+1)

for i in range(h*w,0,-1):
    if i - d < 1:
        break
    x1,y1 = data[i-d-1][1],data[i-d-1][2]
    x2,y2 = data[i-1][1],data[i-1][2]
    '''
    if i - d == 4 and i == 6:
        print(str(x1)+str(y1))
        print(str(x2)+str(y2))
    '''
    dis[i-d] = dis[i] + abs(x1-x2)+abs(y1-y2)

#print(dis) 

q = int(input())

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

Submission status: Accepted

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    n = h * w
    a, q, lr = a[:n], a[n], a[n + 1:]
    index = [0] * n
    for i, _a in enumerate(a):
        index[_a - 1] = i
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    for i in range(d, n):
        diff[i] += diff[i - d]
    return "\n".join([str(diff[r - 1] - diff[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    n = h * w
    a, q, lr = a[:n], a[n], a[n + 1:]
    index = [0] * n
    for i, _a in enumerate(a):
        index[_a - 1] = i
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    for i in range(n):
        if i >= d:
            diff[i] += diff[i - d]
    return "\n".join([str(diff[r - 1] - diff[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    n = h * w
    a, q, lr = a[:n], a[n], a[n + 1:]
    index = [0 for _ in range(n)]
    for i, _a in enumerate(a):
        index[_a - 1] = i
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    for i in range(n):
        if i >= d:
            diff[i] += diff[i - d]
    return "\n".join([str(diff[r - 1] - diff[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [0 for _ in range(n)]
    for i, _a in enumerate(a):
        index[_a - 1] = i
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    for i in range(n):
        if i >= d:
            diff[i] += diff[i - d]
    return "\n".join([str(diff[r - 1] - diff[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [0 for _ in range(n)]
    for i, _a in enumerate(a):
        index[_a - 1] = i
    # index = [a.index(i + 1) for i in range(h * w)]
    diff = [0] * d + [
        abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])
    ]
    costs = []
    for i in range(n):
        if i < d:
            costs.append(diff[i])
        else:
            costs.append(diff[i] + costs[i - d])
    return "\n".join([str(costs[r - 1] - costs[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

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

# 各数字の位置を覚える
pos = [0] * (H * W + 1)
for i in range(H):
    for j in range(W):
        pos[Aij[i][j]] = [i, j]

# 移動累積和を取る
mp_sum = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
    s = pos[i - D]
    e = pos[i]
    mp_sum[i] = mp_sum[i - D] + abs(e[0] - s[0]) + abs(e[1] - s[1])


for lr in LRi:
    mp = mp_sum[lr[1]] - mp_sum[lr[0]]
    print(mp)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    h,w,D = LI()
    a = LIR(h)
    d = defaultdict(int)
    for y in range(h):
        for x in range(w):
            d[a[y][x]] = y*w+x
    n = h*w
    dist = [[0 for i in range(n//D+1)] for i in range(D)]
    for i in range(1,n-D+1):
        y = d[i]//w
        x = d[i]%w
        y_ = d[i+D]//w
        x_ = d[i+D]%w
        k = i%D
        j = i//D
        dist[k][j+1] = dist[k][j]+abs(y_-y)+abs(x_-x)
    q = I()
    for i in range(q):
        l,r = LI()
        k = l%D
        print(dist[k][r//D]-dist[k][l//D])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

    x = [0 for _ in range(90001)]
    y = [0 for _ in range(90001)]
    dp = [0 for _ in range(90001)]

    for i, row in enumerate(A):
        for j, a in enumerate(row):
            x[a] = j
            y[a] = i
    for i in range(D + 1, H * W + 1):
        dp[i] = dp[i - D] + abs(x[i] - x[i - D]) + abs(y[i] - y[i - D])

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


main()

Submission status: Accepted

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

M = []     
for i in range(H*W):
    if i<D:
        M.append(0)    
    else:
        M.append(M[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[i-D][1]))        
        
for L,R in LR:
    print(M[R-1]-M[L-1])