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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w,d = lr()
a = [lr() for i in range(h)]
dic = [[0,0] for i in range(h*w)]
dic1 = [[0] for i in range(d)]
for i in range(h):
    for j in range(w):
        dic[a[i][j]-1] = [i,j]
for j in range(d):
    pre = dic[j]
    for k in range(j,h*w,d):
        cost = abs(pre[0] - dic[k][0])+abs(pre[1] - dic[k][1])
        dic1[j].append(dic1[j][-1]+cost)
        pre = dic[k]
q = ir()
for t in range(q):
    l,r = lr()
    l-=1
    r-=1
    next = (r-l)//d
    start = l%d
    left = l//d+1
    print(dic1[start][left+next]-dic1[start][left])

Submission status: Accepted

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

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

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))

H, W, D = next(inp), next(inp), next(inp)
addr = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        v = next(inp)
        addr[v] = (i, j)

cost = []
for m in range(D):
    arr = [0]
    for x in range((H*W-m)//D):
        if m + x * D == 0:
            arr.append(0)
            continue
        r, c = addr[m + x * D]
        nr, nc = addr[m + (x+1) *D]
        arr.append(arr[-1] + abs(nr - r) + abs(nc - c))
    cost.append(arr)

Q = next(inp)
for _ in range(Q):
    s, t = next(inp), next(inp)
    m = s % D
    ans = cost[m][t//D] - cost[m][s//D]
    print(ans)

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))
q = int(input())
querys = []
for _ in range(q):
    l, r = map(int, input().split())
    querys.append((l-1, r-1))
coor = [None]*(h*w)
for i in range(h):
    for j in range(w):
        coor[a[i][j]-1] = (i, j)
accu = [0]*(h*w)
for i in range(d, h*w):
    px, py = coor[i-d]
    x, y = coor[i]
    accu[i] = accu[i-d] + abs(x-px) + abs(y-py)
for l, r in querys:
    print(accu[r]-accu[l])

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l=[LI() for _ in range(h)]

  q=I()
  ql=[LI() for _ in range(q)]

  dic={}
  for i in range(h):
    for j in range(w):
      x=l[i][j]
      dic[x]=(i+1,j+1)

  n=h*w
  to_last_distance=[0]*n
  for i in range(1,n+1)[::-1]:
    if i+d<=n:
      i_y,i_x=dic[i]
      ipd_y,ipd_x=dic[i+d]
      to_last_distance[i-1]=to_last_distance[i+d-1]
      to_last_distance[i-1]+=(abs(i_y-ipd_y)+abs(i_x-ipd_x))

  # print(to_last_distance)

  ans=[]
  for st,ed in ql:
    ans.append(to_last_distance[st-1]-to_last_distance[ed-1])

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, D = NMI()
    grid = [NLI() for i in range(H)]
    Q = NI()
    querys = [NLI() for i in range(Q)]

    point = [[-1,-1] for _ in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            a = grid[h][w]
            point[a] = [h, w]

    cost_S = [0] * (H*W + 1)
    for c in range(H*W + 1):
        if c <= D:
            continue

        cost_S[c] = cost_S[c-D] + abs(point[c][0] - point[c-D][0]) + abs(point[c][1] - point[c-D][1])

    for query in querys:
        l, r = query
        print(cost_S[r] - cost_S[l])


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)]
e=[[] for _ in range(h*w+1)]
dp=[0]*(h*w+1)
for i in range(h):
  for j in range(w):
    e[a[i][j]]=(i,j)
for i in range(1,h*w+1-d):
  dp[i+d]=dp[i]+abs(e[i+d][0]-e[i][0])+abs(e[i+d][1]-e[i][1])
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  print(dp[r]-dp[l])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,d = list(map(int, input().split()))
a = [None]*h
n = h*w
dd = [None]*(n)
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j,num in enumerate(a[i]):
        dd[num-1] = (i,j)
vals = [[] for _ in range(d)]
for i in range(d):
    l = []
    prev = i
    s = 0
    for j in range(i, n, d):
        v = abs(dd[j][0]-dd[prev][0]) + abs(dd[j][1]-dd[prev][1])
        s += v
        l.append(s)
        prev = j
    vals[i] = l
q = int(input())
ans = [None]*q
for i in range(q):
    ll,rr = map(lambda x: int(x)-1, input().split())
    ans[i] = vals[rr%d][rr//d] - vals[ll%d][ll//d]
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
table = [[-1,-1] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a > D:
            table[a-D][0] = i
            table[a-D][1] = j
magic = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a <= H*W-D:
            magic[a] = abs(i-table[a][0])+abs(j-table[a][1])
for i in range(D+1,H*W+1):
    magic[i] += magic[i-D]
Q = int(input())
ans = 0
for i in range(Q):
    L,R = map(int,input().split())
    if L == R:
        print(0)
    else:
        if L <= D:
            print(magic[R-D])
        else:
            print(magic[R-D]-magic[L-D])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
d, px, py = [0]*(H*W+1), [0]*(H*W+1), [0]*(H*W+1)

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

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

# print(d)

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    H, W, D = map(int, input().split())
    place = {}
    for i in range(H):
        A = list(map(int, input().split()))
        for j in range(W):
            place[A[j] - 1] = (i, j)
    magic = [0] * (H * W)
    for n in range(D):
        val = n
        x, y = place[val]
        while val + D < H * W:
            nx, ny = place[val + D]
            magic[val + D] = abs(nx - x) + abs(ny - y) + magic[val]
            val += D
            x, y = nx, ny
    #print(magic)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
dic = {}
memo = [0]*(H*W+1)

for i in range(H):
  s = input().split()
  for j in range(W):
    dic[int(s[j])] = (i,j)
    
for i in range(1,H*W+1):
  if i - D >= 1:
    memo[i] = memo[i-D] + abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
    
Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(memo[r]-memo[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())
L,R=[],[]
for i in range(Q):
  L.append(list(map(int,input().split())))
  R.append(L[i][1])
  L[i]=L[i][0]
B=dict()
for i in range(H):
  for j in range(W):
    B[A[i][j]]=(i,j)
C=[[0,0] for i in range(D)]
for i in range(1,D):
  for j in range(i+D,H*W+1,D):
    C[i].append(C[i][-1]+abs(B[j][0]-B[j-D][0])+abs(B[j][1]-B[j-D][1]))
for j in range(D+D,H*W+1,D):
  C[0].append(C[0][-1]+abs(B[j][0]-B[j-D][0])+abs(B[j][1]-B[j-D][1]))
for i in range(Q):
  print(C[R[i]%D][(R[i]+D-1)//D]-C[L[i]%D][(L[i]+D-1)//D])

Submission status: Accepted

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

for i in range(H):
    for j in range(W):
        lst[A[i][j]-1] = [j, i]
tr = [[0] for _ in range(D)]
for i in range(D):
    for j in range(i+D, W*H, D):
        dlt = abs(lst[j][0] - lst[j-D][0]) + abs(lst[j][1] - lst[j-D][1])
        tr[i].append(tr[i][-1] + dlt)

Q = int(input())

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

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))
print(*result, sep='\n')

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))
#print(*result, sep='\n')

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
a = [0]*h
for i in range(h):
    a[i] = list(map(int,input().split()))
num = [[] for i in range(w*h+1)]
for i in range(h):
    for j in range(w):
        num[a[i][j]].append([i,j])
s = [0]*(h*w+1)
for i in range(1,h*w-d+1):
    s[d+i] = s[i] + abs(num[d+i][0][0]-num[i][0][0]) + abs(num[d+i][0][1]-num[i][0][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:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    H, W, D = in_nn()
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q = in_n()
    LR = [list(map(int, readline().split())) for _ in range(Q)]

    grid = [tuple()] * (H * W + 1)
    for y in range(H):
        for x in range(W):
            num = A[y][x]
            grid[num] = (x + 1, y + 1)

    move = [[] for _ in range(D)]
    for i in range(D):
        if i == 0:
            s = D
        else:
            s = i
        while s <= H * W:
            move[i].append(grid[s])
            s += D

    d = [[] for _ in range(D)]
    for i in range(D):
        d[i].append(0)
        for j in range(len(move[i]) - 1):
            x, y = move[i][j]
            nx, ny = move[i][j + 1]
            d[i].append(abs(nx - x) + abs(ny - y))

    for i in range(D):
        for j in range(len(d[i]) - 1):
            d[i][j + 1] += d[i][j]

    # print(d)

    ans = [0] * Q
    for i in range(Q):
        l, r = LR[i]
        q1, rr = divmod(l, D)
        q2, _ = divmod(r, D)
        if rr == 0:
            ans[i] = d[rr][q2 - 1] - d[rr][q1 - 1]
        else:
            ans[i] = d[rr][q2] - d[rr][q1]

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


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

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

acc=[0]*(h*w)
for i in range(h*w):
    if i>=d:
        _to=nums[i+1]
        _from=nums[i+1-d]
        acc[i]+=acc[i-d]+abs(_from[0]-_to[0])+abs(_from[1]-_to[1])

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

Submission status: Accepted

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

base = []
for h in range(H):
    num = list(map(int, input().split()))
    for w in range(W):
        base.append((num[w], h+1, w+1))

base.sort(key=lambda tup:tup[0])
dist = [0]*(W*H+D+1)
for i in range(W*H-D):
    wei1, h1, w1 = base[i]
    wei2, h2, w2 = base[i+D]
    dist[i+D] = dist[i] + abs(h1-h2) + abs(w1-w2)

Q = int(input())
for _ in range(Q):
    p0, p1 = map(int, input().split())
    print(abs(dist[p1-1]-dist[p0-1]))

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

l = []

for h in range(H):
    for w in range(W):
        l.append((A[h][w], w, h))

l.sort()

S = [0] * (H * W + D + 10)

for i, x, y in l:
    if i + D <= H * W:
        _, xx, yy = l[i + D - 1]
        S[i + D] = abs(xx - x) + abs(yy - y) + S[i]

Q = int(input())

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc089/tasks/abc089_d

def calc(x):
    if x<D+1:
        mv[x]=0
        return 0
    else:
        p = d[x][0]
        q = d[x][1]
        r = d[x-D][0]
        s = d[x-D][1]
        tmp = abs(p-r)+abs(q-s)
        ret= tmp+calc(x-D)
        mv[x]=ret
        return ret
####################################################################
import sys 
sys.setrecursionlimit(10**5)
H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())

d=dict()
z=0
for a in A:
    for b in a:
        p = z//W
        q = z%W
        d[b]=(p,q)
        z+=1
        
mv=[0]*(H*W+1)
for i in range(D):
    calc(H*W-i)
    #print(H*W-i,calc(H*W-i))    
#print(mv)

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

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
px = [0]*90001
py = [0]*90001
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(len(A)):
        px[A[j]] = i+1
        py[A[j]] = j+1
d = [0]*90001
Q = int(input())
for i in range(D+1,H*W+1,1):
    d[i] = d[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D])
for _ in range(Q):
    l,r = map(int,input().split())
    print(d[r]-d[l])

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,d = map(int,ipt().split())
    pl = [(-1,-1)]*(h*w+1)
    for i in range(h):
        a = [int(i) for i in ipt().split()]
        for j,aj in enumerate(a):
            pl[aj] = (i,j)
    ssl = [0]*(h*w+1)
    for i in range(d+1,h*w+1):
        ssl[i] = ssl[i-d]+abs(pl[i-d][0]-pl[i][0])+abs(pl[i-d][1]-pl[i][1])
    q = int(ipt())
    for _ in range(q):
        l,r = map(int,ipt().split())
        print(ssl[r]-ssl[l])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]-1]=[i,j]
#print(lis)

costs=[0 for i in range(h*w+1)]
for i in range(1,d+1):
    for j in range(0,h*w):
        if i+d*(j+1)<h*w+1:
            costs[i+d*(j+1)]=costs[i+d*j]+abs(lis[i+d*(j+1)-1][1]-lis[i+d*j-1][1])+abs(lis[i+d*(j+1)-1][0]-lis[i+d*j-1][0])
        else:
            break
q=I()
for i in range(q):
    l,r=MI()
    u=l%d
    print(costs[r]-costs[l])

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

    x = [0] * (h*w)
    y = x.copy()
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            x[a[j] - 1] = i
            y[a[j] - 1] = j

    # 累積和
    cost = [[0] for _ in range(d)]
    for i in range(d, h*w):
        cost[i%d].append(cost[i%d][-1] + abs(x[i]-x[i-d]) + abs(y[i]-y[i-d]))

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

    for i in ans:
        print(i)

main()

Submission status: Accepted

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

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

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

for i in range(h):
    for j in range(w):
        s = ab[i][j]
        dp[s] =[i,j]
        
dpp= [0]*(h*w+1)

for k in range(d+1,h*w+1):
#    print(k)
    dpp[k] = dpp[k-d] + abs(dp[k][0]-dp[k-d][0]) +abs(dp[k][1]-dp[k-d][1])
    
q = int(input())

for x in range(q):
    a,b = map(int, input().split())
    print(dpp[b]-dpp[a])

Submission status: Accepted

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

  A=[[0,0] for i in range(H*W)]
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A[~-a][0],A[~-a][1]=h,w

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

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

main()

Submission status: Accepted

Solution code:
def main():
  H,W,D=map(int,input().split())
  A=[]
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A+=[[a,h,w]]
  A.sort(key=lambda x:x[0])

  B=[0]*(H*W)
  for i in range(D):
    while i+D<W*H:
      B[i+D]=B[i]+abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D

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

main()

Submission status: Accepted

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

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

  B=[0]*(H*W)
  for i in range(D):
    while i+D<W*H:
      B[i+D]=B[i]+abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D

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

main()

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
adr = [-1]*(h*w) #indexの数字は[i,j]に書かれている
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        adr[a[j]-1] = [i,j]
        
cost = [0]*(h*w)
for i in range(d,h*w):
    cost[i] = cost[i-d] + abs(adr[i][0]-adr[i-d][0]) + abs(adr[i][1]-adr[i-d][1])
        
q = int(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    ans.append(cost[r-1]-cost[l-1])

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l=[[] for t in range(h*w)]
for i in range(h):
  ll=list(map(int,input().split()))
  for j in range(w):
    l[ll[j]-1]=[i,j]
    
r=[[0] for dd in range(d)]
for dd in range(d):
  if dd==0:
    k=d
  else:
    k=dd
  while k+d<=h*w:
    r[dd].append(r[dd][-1]+abs(l[k+d-1][0]-l[k-1][0])+abs(l[k+d-1][1]-l[k-1][1]))
    k+=d

    
q=int(input())
for qq in range(q):
  a,b=map(int,input().split())
  if a%d==0:
    p=d
  else:
    p=a%d
  aa=(a-p)//d
  bb=(b-p)//d
  ans=r[a%d][bb]-r[a%d][aa]
  print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import defaultdict
    from itertools import accumulate

    h, w, d = map(int, readline().split())
    dict = defaultdict(list)
    memo = [[0] for _ in range(d + 1)]
    for i in range(h):
        a = list(map(int, readline().split()))
        for j, aa in enumerate(a):
            dict[aa] = [i, j]
    for i in range(1, d + 1):
        bf = i
        for af in range(i + d, h * w + 1, d):
            memo[i].append(abs(dict[bf][0] - dict[af][0]) + abs(dict[bf][1] - dict[af][1]))
            bf = af
        memo[i] = list(accumulate(memo[i]))
    q = int(readline())
    for _ in range(q):
        l, r = map(int, readline().split())
        if r < l:
            r, l = l, r
        l, i = divmod(l, d)
        r //= d
        if i == 0:
            i = d
            l -= 1
            r -= 1
        print(memo[i][r] - memo[i][l])


if __name__ == '__main__':
    main()