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 = tuple(map(int,input().split()))

a = [[int(t)for t in input().split()]for _ in [0]*h]

pos = [0]*(h*w)

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

cusum = [0]*d


for i in range(h*w-d):
  x,y = pos[i]
  z,w = pos[i+d]
  cost = abs(x-z)+abs(y-w)
  cusum.append(cusum[-d]+cost)

q = int(input())

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    Q = int(input())
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    B = [10**9]*(H*W+1)
    pos = {A[i][j]: (i+1, j+1) for i in range(H) for j in range(W)}
    for i in range(1, H*W+1):
        cur_p = i
        if B[cur_p] < 10**9:
            continue
        B[cur_p] = 0
        y, x = pos[cur_p]
        while cur_p + D <= H*W:
            np = cur_p + D
            ny, nx = pos[np]
            power = abs(nx - x) + abs(ny - y)
            B[np] = B[cur_p] + power
            cur_p = np
            y, x = ny, nx

    for le, ri in LR:
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

M = [[0 for _ in range(W)] for i in range(H)]

num = [[] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        num[A[i][j]].append([i,j])

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

for i in range(D,H*W+1):
    if i <= D:
        continue
    else:
        dist[i] = dist[i-D] + abs(num[i][0][0]-num[i-D][0][0]) + abs(num[i][0][1]-num[i-D][0][1])

##print(dist)
Q = int(input())

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

Submission status: Accepted

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

B = [0]*(h*w)

C = [0]*(h*w)

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

for i in range(h*w):
    if i-d >= 0:
        j = i-d
        px, py = B[j]
        x, y = B[i]
        C[i] = abs(x-px)+abs(y-py)+C[j]
    else:
        C[i] = 0
#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:
import sys
input = sys.stdin.readline
from collections import *

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

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

x[0] = x[D]
y[0] = y[D]
acc = [[0] for _ in range(D)]

for i in range(D):
    now = i
    
    while now+D<=H*W:
        acc[i].append(acc[i][-1]+abs(x[now+D]-x[now])+abs(y[now+D]-y[now]))
        now += D

Q = int(input())

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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
b=[(0--(h*w-i)//d)*[0]for i in range(d)]
a=[list(map(int,input().split()))for _ in range(h)]
for i in range(h):
  for j in range(w):
    a[i][j]-=1
    b[a[i][j]%d][a[i][j]//d]=(i,j)
bb=[[0]for _ in range(d)]
for i in range(d):
  for j in range(1,len(b[i])):
    bb[i].append(bb[i][-1]+(abs(b[i][j-1][0]-b[i][j][0])+abs(b[i][j-1][1]-b[i][j][1])))
for ll,rr in [list(map(int,input().split()))for _ in range(int(input()))]:
  l=ll-1
  r=rr-1
  print(bb[l%d][r//d]-bb[l%d][l//d])

Submission status: Accepted

Solution code:
import itertools
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
p = [0] * (h * w)
for i, j in itertools.product(range(h), range(w)):
  p[a[i][j] - 1] = (i, j)
s = [0] * d
for i in range(h * w - d):
  s.append(s[-d] + abs(p[i][0] - p[i+d][0]) + abs(p[i][1] - p[i+d][1]))
q = int(input())
for i in range(q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  print(s[r] - s[l])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

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

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

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

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        ti[j + 1] += ti[j]

Q = int(input())
result = []
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    result.append(t[i][(R - i) // D] - t[i][(L - i) // D])
print('\n'.join(str(i) for i in result))

Submission status: Accepted

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

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        t[i][j + 1] += t[i][j]

Q = int(input())
result = []
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    result.append(t[i][(R - i) // D] - t[i][(L - i) // D])
print('\n'.join(str(i) for i in result))

Submission status: Accepted

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

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        t[i][j + 1] += t[i][j]

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

Submission status: Accepted

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

d = {}
for y in range(H):
    Ay = A[y]
    for x in range(W):
        d[Ay[x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(ti) - 1):
        ti[j + 1] += ti[j]

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

Submission status: Accepted

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

d = {}
for y in range(H):
    Ay = A[y]
    for x in range(W):
        d[Ay[x]] = (y, x)

t = [[0] * ((H * W + D - 1) // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(ti) - 1):
        ti[j + 1] += ti[j]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,D=map(int,input().split())
    A=[() for _ in range(H*W)]
    for i in range(H):
        a=list(map(int1,input().split()))
        for j,x in enumerate(a):
            A[x]=(i,j)
    c=[[0] for _ in range(D)]
    for i in range(D):
        for k,j in enumerate(range(i,H*W-D,D)):
            c[i].append(c[i][k]+abs(A[j][0]-A[j+D][0])+abs(A[j][1]-A[j+D][1]))
    Q=int(input())
    for _ in range(Q):
        L,R=map(int1,input().split())
        print(c[L%D][R//D]-c[L%D][L//D])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

x = [[-1] for _ in range(h*w+d+1)]
m = []
for i in range(h):
    for j in range(w):
        x[a[i][j]] = [i, j]
        m.append([a[i][j], i, j])
m.sort()
visit = [[-1 for _i in range(w)] for _j in range(h)]

for pos, xx, yy in m:
    if visit[xx][yy] < 0:
        visit[xx][yy] = 0
        while x[pos+d][0] >= 0:
            g, h = x[pos+d]
            visit[g][h] = visit[xx][yy] + abs(g-xx)+abs(h-yy)
            xx = g
            yy = h
            pos = a[xx][yy]
for l, r in lr:
    print(visit[x[r][0]][x[r][1]]-visit[x[l][0]][x[l][1]])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

P=defaultdict(list)
for d in range(1,D+1):
    a=d
    while a+D<=H*W:
        p=abs(M[a][0]-M[a+D][0])+abs(M[a][1]-M[a+D][1])
        if P[d]:
            P[d].append(P[d][-1]+p)
        else:
            P[d]=[0,p]
        a+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    d=L%D
    l=L//D
    r=R//D
    if d==0:
        d=D
        if len(P[d])>0:
            print(P[d][r-1]-P[d][l-1])
        else:
            print(0)
    else:
        if len(P[d])>0:
            print(P[d][r]-P[d][l])
        else:
            print(0)

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = [[]]
for i in range(H):
  A.append([0]+list(map(int,input().split())))
la = [[] for o in range(H*W+1)]
for i in range(1,H+1):
  for j in range(1,W+1):
    la[A[i][j]].append(i)
    la[A[i][j]].append(j)
Q = int(input())
q = []
for i in range(Q):
  q.append(list(map(int,input().split())))

l = [[0]+[0 for i in range((H*W-j)//D)] for j in range(D)]
#あまり0は特別扱い
i = 0
v = l[i]
for j in range(1,len(l[0])-1):
  mae = i + D*j
  ato = i + D*(j+1)
  v[j+1] = v[j] + abs(la[mae][0]-la[ato][0]) + abs(la[mae][1]-la[ato][1])
#あまり1~D-1まで
for i in range(1,D):
  v = l[i]
  for j in range(len(v)-1):
    mae = i + D*j
    ato = i + D*(j+1)
    v[j+1] = v[j] + abs(la[mae][0]-la[ato][0]) + abs(la[mae][1]-la[ato][1])

for i in range(Q):
  L,R = q[i][0],q[i][1]
  amari = L%D
  haji = (L-amari)//D
  owari = (R-amari)//D  
  print(l[amari][owari]-l[amari][haji])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
h,w,d=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        pos[a[j]]=(i,j)
ans=[0]*(h*w+1)
visited=[True]*(h*w+1)
def dfs(s,nxt):
    if nxt>h*w:
        return 
    visited[s]=False
    dfs(nxt,nxt+d)
    x,y=pos[s]
    nx,ny=pos[nxt]
    ans[s]+=ans[nxt]+abs(nx-x)+abs(ny-y)
for i in range(1,h*w+1):
    if visited[i]:
        dfs(i,i+d)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(ans[l]-ans[r])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]
    P = defaultdict(list)
    for d in range(1, D + 1):
        a = d
        while a <= H * W - D:
            p = abs(M[a][0] - M[a + D][0]) + abs(M[a][1] - M[a + D][1])
            if P[d]:
                P[d].append(P[d][-1] + p)
            else:
                P[d] = [0, p]
            a += D
    # print(P)
    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = L % D
        l = L // D
        r = R // D
        if d == 0:
            d = D
            if len(P[d]) > 0:
                print(P[d][r - 1] - P[d][l - 1])
            else:
                print(0)
        else:
            if len(P[d])>0:
                print(P[d][r] - P[d][l])
            else:
                print(0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

    diff = dict()
    for d in range(1, D + 1):
        cumsum = [0]
        ds = list(range(d, H * W + 1, D))
        N = len(ds)
        for i in range(N - 1):
            x, y = place[ds[i]]
            X, Y = place[ds[i + 1]]
            tmp = cumsum[-1] + abs(x - X) + abs(y - Y)
            cumsum.append(tmp)
        diff[d % D] = cumsum

    Q = int(input())
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        m = L % D
        if m == 0:
            L_idx = L // D - 1
            R_idx = R // D - 1
        else:
            L_idx = L // D
            R_idx = R // D
        a = diff[m][R_idx] - diff[m][L_idx]
        ans.append(a)

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

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

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
G=[[]]*(H*W)
J=[0]*(H*W)
for i in range(H):
  for j,a in enumerate(list(map(int,input().split()))):
    G[a-1]=[i,j]
    
for i in range(H*W):
  if i-D>=0:
    J[i]=J[i-D]+abs(G[i][0]-G[i-D][0])+abs(G[i][1]-G[i-D][1])
      
for i in range(int(input())):
  l,r=map(int,input().split())
  print(J[r-1]-J[l-1])

Submission status: Accepted

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

lst=[[]for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        lst[A[i][j]-1].append(i)
        lst[A[i][j]-1].append(j)
#print(lst)
#print(lst[1][1])
d=[]
for i in range(D):
    cnt=[0]
    for j in range(i+D,H*W,D):
        cnt.append(cnt[-1]+abs(lst[j][0]-lst[j-D][0])+abs(lst[j][1]-lst[j-D][1]))
    d.append(cnt)
ans=[]
#print(cnt)
#print(d)
for i in range(Q):
    l,r=map(int,input().split())
    ll=(l-1)%D
    count=d[ll]
    r-=1
    l-=1
    #print(count)
    vall=count[l//D]
    #print(l//D)
    #print(r//D)
    valr=count[r//D]
    val=valr-vall
    #print(val)
    ans.append(val)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:



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

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


accum = [0] * (H*W)

for i in range(D):
    j = 0
    while i + j*D <= (H*W) - 1:
        if j == 0:
            accum[i + j*D] = 0
        else:
            curr = i + j*D
            prev = i + (j-1)*D
            accum[curr] = accum[prev] + abs(num[prev][0] - num[curr][0]) + abs(num[prev][1] - num[curr][1])

        j += 1

for l,r in LR:
    print(accum[r-1] - accum[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)]
dic={}
for i in range(H):
    for j in range(W):
        dic[A[i][j]]=(i,j)
dist=[0]*(H*W+10)
for i in range(D+1,H*W+1):
    xd=abs(dic[i][0]-dic[i-D][0])
    yd=abs(dic[i][1]-dic[i-D][1])
    dist[i]=dist[i-D]+xd+yd
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    print(dist[R]-dist[L])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
A=[]
for _ in range(h):
    A.append([int(i) for i in input().split()])
q=int(input())
lr=[]
for _ in range(q):
    l,r = map(int,input().split())
    lr.append((l,r))
D=dict()
for i in range(h):
    for j in range(w):
        D[A[i][j]]=(i,j)

def dist(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
#ans=[[-1 for _ in range(h*w//d+1)] for _ in range(d)]
res=dict()
for i in range(d):
    j=i+1
    cnt=0
    res[j]=0
    #ans[i][0] = 0
    while j<=h*w-d:
        #ans[i][cnt+1] = ans[i][cnt] + dist(D[j],D[j+d])
        res[j+d] = res[j]+dist(D[j],D[j+d]) #ans[i][cnt]
        j+=d
        cnt+=1
for l,r in lr:
    print(res[r]-res[l])

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
A = []
L = [None for _ in range(H * W)]
for _ in range(H):
    A.append(list(map(int,input().split())))
for i in range(H):
    for j in range(W):
        L[A[i][j]-1] = [i, j]
Q = int(input())
cnt = [[0] for _ in range(D)]
for i in range(D):
    j = i
    while j + D <= H * W - 1:
        cnt[i].append(cnt[i][-1] + abs(L[j + D][0] - L[j][0]) + abs(L[j + D][1] - L[j][1]))
        j += D
for _ in range(Q):
    L, R = map(int,input().split())
    i = (L - 1) % D
    print(cnt[i][(R-1)//D] - cnt[i][(L-1)//D])

Submission status: Accepted

Solution code:
#19:38
#20:19

H,W,D = map(int,input().split())
MAX = H*W
A = [list(map(int,input().split())) for i in range(H)]
Point = [0]*(MAX+1)
for h in range(H):
    for w in range(W):
        Point[A[h][w]] = (h,w)
K = []
for i in range(1,D+1):
    List = []
    n = i
    h,w = Point[n]
    cost = 0
    while n<=MAX:
        y,x = Point[n]
        cost += abs(h-y)+abs(w-x)
        List.append(cost)
        h,w = y,x
        n+=D
    K.append(List)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    a,l,r = (L-1)%D,(L-1)//D,(R-1)//D
    print(K[a][r]-K[a][l])

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())))
dic=dict()
for i in range(h):
    for j in range(w):
        dic[a[i][j]] = (i, j)
co_order = [None] + [value for key, value in sorted(dic.items(), key=lambda x: x[0])]
cost = {i: [0] for i in range(1, d + 1)}

for i in range(1, d + 1):
    sx, sy= co_order[i]
    for ex, ey in co_order[i+d::d]:
        cost[i].append(cost[i][-1] + abs(sx - ex) + abs(sy - ey))
        sx, sy = ex, ey
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    index = (r-1)%d+1
    print(cost[index][(r-1)//d] - cost[index][(l-1)//d])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
li = [-1]*h*w

for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        li[a[j]-1] = (i,j)

li2 = [[] for _ in range(d)]
li3 = [[0] for _ in range(d)]
for i in range(d):
    li_tmp = li[i::d]
    for j in range(len(li_tmp)-1):
        li2[i].append(abs(li_tmp[j][0]-li_tmp[j+1][0]) + abs(li_tmp[j][1]-li_tmp[j+1][1]))

for i in range(d):
    for j in range(len(li2[i])):
        if j == 0:
            li3[i].append(li2[i][j])
        else:
            li3[i].append(li3[i][-1] + li2[i][j])

q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    l1 = l % d
    print(li3[l1][r//d] - li3[l1][l//d])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

H,W,D = LI()
A = [_LI() for _ in range(H)]
Q = NI()
LR = [_LI() for _ in range(Q)]

dist =  [[0 for _ in range(math.ceil(H*W/D))] for _ in range(D)]
S  = []
for i in range(H):
    for j in range(W):
        S.append((A[i][j],i,j))
S.sort()

for a,i,j in S[D:]:
    dist[a%D][a//D] = dist[a%D][a//D-1] + abs(S[a-D][1]-i) + abs(S[a-D][2]-j)

for l,r in LR:
    ans = dist[r%D][r//D] - dist[l%D][l//D]
    print(ans)

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
a1=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
for i in range(h):
  i+=1
  tmp=list(map(int,input().split()))
  for j in range(w):
    num=tmp[j]
    j+=1
    a[num%d][int( (num-1)/d)]=[i,j]
for i in range(len(a)):
  a1[i][0]=0
  for j in range(len(a[i])-1):
    j=j+1
    if a[i][j]!=[]:
      a1[i][j]=a1[i][j-1]+abs(a[i][j][0]-a[i][j-1][0])+abs(a[i][j][1]-a[i][j-1][1])

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

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
grid = []
memo = [[] for _ in range(H*W+1)]
for i in range(H):
    grid.append(list(map(int, input().split())))
    for j in range(len(grid[i])):
        memo[grid[i][j]].append(i)
        memo[grid[i][j]].append(j)

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

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

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
h,w,d = ma()
area_d = [[] for i in range(d)]
rs = [[0] for i in range(d)]
for i in range(h):
    for j,a in enumerate(ma()):
        area_d[a%d].append((a,i,j))
for i in range(d):
    area_d[i].sort()

for i in range(d):
    yp,xp = 0,0
    for a,y,x in area_d[i]:
        rs[i].append(rs[i][-1] + abs(y-yp)+abs(x-xp))
        yp,xp = y,x
q = int(input())
for i in range(q):
    l,r = ma()
    lq,lr = divmod(l,d)
    rq,rr = divmod(r,d)
    if lr==0:print(rs[lr][rq] - rs[lr][lq])
    else:print(rs[lr][rq+1] - rs[lr][lq+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())))

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

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

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split(" "))
mass = [[0 for _ in range(W)] for _ in range(H)]
num = [[0,0] for _ in range(H * W + 1)]
DP = [0 for _ in range(H * W + 1)]
for i in range(H):
  mass[i] = list(map(int,input().split(" ")))
for i in range(H):
  for i2 in range(W):
    num[mass[i][i2]] = [i,i2]
for i in range(D,W * H + 1):
  DP[i] = DP[i - D] + abs(num[i][0] - num[i - D][0]) + abs(num[i][1] - num[i - D][1])
L = 0
R = 0
ans = 0
Q = int(input())
for i in range(Q):
  ans = 0
  L,R = map(int,input().split(" "))
  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())
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = {}
for i in range(H):
    for j in range(W):
        ctr[A[i][j]] = (i, j)

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

for l, r in X:
    print(memo[r] - memo[l])

Submission status: Accepted

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

for i in range(H):
    for j, A in enumerate(map(int, input().split(" "))):
        coord[A] = (i, j)

magic = [0 for i in range(H * W + 1)]
for i in range(H * W + 1):
    if i + D <= H * W:
        magic[i + D] += magic[i]
        if i != 0:
            magic[i + D] += abs(coord[i][0] - coord[i + D][0]) + abs(coord[i][1] - coord[i + D][1])

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

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)]
    pos = [[-1,-1] for _ in range(H*W)]
    for i in range(H):
        for j in range(W):
            pos[a[i][j]-1][0] = i
            pos[a[i][j]-1][1] = j
    
    def manhattan_dist(x1,y1,x2,y2):
        return abs(x2-x1)+abs(y2-y1)

    ans_list = [[0] for _ in range(D)]
    for i in range(D):
        do = -(-(H*W-i)//D)
        for j in range(do-1):
            x1,y1 = pos[D*j+i]
            x2,y2 = pos[D*(j+1)+i]
            md = manhattan_dist(x1,y1,x2,y2)
            ans_list[i].append(ans_list[i][-1]+md)
    
    Q = int(input())
    for _ in range(Q):
        a,b = map(int,input().split())
        mod = a%D-1
        u = -(-a//D)-1
        w = -(-b//D)-1
        print(ans_list[mod][w]-ans_list[mod][u])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    height, width, difference = map(int, input().split())
    grid = [[int(x) for x in input().split()] for _ in range(height)]
    coordinate = [[] for _ in range(height * width + 1)]
    cost = [0 for _ in range(height * width + 1)]
    for i in range(height):
        for j in range(width):
            coordinate[grid[i][j]] = [i, j]
    for i in range(difference + 1, height * width + 1):
        cost[i] += cost[i - difference]
        cost[i] += abs(coordinate[i][0] - coordinate[i - difference][0]) + abs(coordinate[i][1] - coordinate[i - difference][1])
    queries = int(input())
    for _ in range(queries):
        left, right = map(int, input().split())
        print(cost[right] - cost[left])


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())
lr = [list(map(int, input().split())) for i in range(q)]
spot = [0] * (h*w)
for ki,v in enumerate(a):
  for kj,i in enumerate(v):
    spot[i-1] = (ki,kj)
cumsum = [[0] for i in range(d)]
for start in range(d):
  for j in range(start,h*w-d,d):
    h1,w1 = spot[j]
    h2,w2 = spot[j+d]
    dist = abs(h1-h2) + abs(w1-w2)
    cumsum[start].append(dist+cumsum[start][-1])
for l,r in lr:
  l -= 1
  r -= 1
  mod = l % d
  L,R = l//d,r//d
  ans = cumsum[mod][R]-cumsum[mod][L]
  print(ans)

Submission status: Accepted

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

whereA = [[0,0] for _ in range(h*w)]
for i in range(h):
    A = list(map(int,input().split()))
    for j,a in enumerate(A):
        whereA[a-1] = [i,j]

Dsum = [0]*(h*w)
for i in range(h*w):
    Dsum[i] = Dsum[max(i-d,i%d)] + abs(whereA[i][0]-whereA[max(i-d,i%d)][0]) + abs(whereA[i][1]-whereA[max(i-d,i%d)][1])

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:
#ABC089-D Practical Skill Test
"""
全てのクエリをO(1)で求められるようにメモ化すればok
1~H*Wの数字がどのマスに書いてあるのかを求める。(数字→座標を調べられるようにする)
そうしたときに、D個前のコストを足し合わせる累積和という方法を用いて各クエリO(1)で求められるようになる
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

h,w,d = map(int,readline().split())
A = []
for i in range(h):
    A.append(list(map(int,readline().split())))

cor = [[] for _ in range(h*w)]
for i,a in enumerate(A):
    for j,b in enumerate(a):
        cor[b-1] = [i,j]

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


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