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

idx=[0]*(H*W)
for h in range(H):
    for w in range(W):
        num=A[h][w]
        idx[num-1]=[h+1,w+1]
acum=[0]*(H*W+1)
for i in range(1,H*W+1):
    if i-D<=0:
        acum[i]=sum(idx[i-1])
    else:
        prex,prey=idx[i-1-D]
        nexx,nexy=idx[i-1]
        acum[i]=acum[i-D]+abs(nexx-prex)+abs(nexy-prey)
#print(acum)


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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    H, W, D = map(int, input().split())
    B = [0] * (H * W)

    C = [None] * (H * W)
    for r in range(H):
        for c, cell in enumerate(int(x) - 1 for x in input().split()):
            C[cell] = r, c

    for x in range(D, H * W):
        L, R = x - D, x
        lr, lc = C[L]
        rr, rc = C[R]
        B[R] = B[L] + abs(rr - lr) + abs(rc - lc)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dist(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
G = {}
for i in range(H):
    for j in range(W):
        G[A[i][j]] = (i,j)
C = {}
for j in range(1,D+1):
    k = 1
    C[j] = 0
    while j+k*D<=H*W:
        C[j+k*D] = C[j+(k-1)*D]+dist(G[j+(k-1)*D],G[j+k*D])
        k += 1
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())
MAX = H*W
#M = MAX//D+1
dic = {}

for i in range(H):
  temp = list(map(int,input().split()))
  for j in range(W):
    now = temp[j]
    dic[now] = (i,j)
#print(dic)
L = [[0] for _ in range(D)]
for i in range(D): #MODで0からD-1をひたすら見ていく。
  if i == 0:
    now = D
  else:
    now = i
  while now+D <= MAX:
    tsugi = now+D
    np = dic[now] #今の場所
    tp = dic[tsugi]
    dis = abs(np[0]-tp[0])+abs(np[1]-tp[1])
    L[i].append(L[i][-1]+dis)
    now = tsugi
#print(L)
Q = int(input())
for i in range(Q):
  left,right = map(int,input().split())
  MOD = left%D
  #print(L[MOD])
  start = (left-1)//D
  end = (right-1)//D
  ans = L[MOD][end]-L[MOD][start]
  print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    B = [0] * (H * W)

    C = [None] * (H * W)
    for r, row in enumerate(A):
        for c, cell in enumerate(row):
            C[cell - 1] = r, c

    for x in range(D, H * W):
        L, R = x - D, x
        lr, lc = C[L]
        rr, rc = C[R]
        B[R] = B[L] + abs(rr - lr) + abs(rc - lc)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    B = [[] for _ in range(D)]

    C = [None] * (H * W)
    for r, row in enumerate(A):
        for c, cell in enumerate(row):
            C[cell - 1] = r, c

    for x in range(H * W):
        r = x % D
        if B[r]:
            cr, cc = C[x]
            pr, pc = C[x - D]
            cost = abs(cr - pr) + abs(cc - pc)
            B[r].append(B[r][-1] + cost)

        else:
            B[r].append(0)

    ans = []
    Q = int(input())
    for _ in range(Q):
        L, R = (int(x) - 1 for x in input().split())
        r = R % D
        ql, qr = L // D, R // D

        ans.append(B[r][qr] - B[r][ql])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, d = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    q = int(input())

    XY = [[] for _ in range(H * W)]
    for h in range(H):
        for w in range(W):
            XY[A[h][w] - 1] = [h, w]
    R = [0] * (H * W + 1)
    for i in range(1, H * W + 1):
        if i - d > 0:
            x1, y1 = XY[i - 1]
            x2, y2 = XY[i - 1 - d]
            cost = abs(x1 - x2) + abs(y1 - y2)
            R[i] = R[i - d] + cost

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

from collections import defaultdict

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

dic = defaultdict(list)

for h in range(H):
    for w in range(W):
        dic[A[h][w]] = [h, w]

def calc(l, r):
    return abs(dic[l][0] - dic[r][0]) + abs(dic[l][1] - dic[r][1])

lst = [0] * (H * W + 1)
for d in range(1, D + 1):
    tmp = d
    while tmp + D <= (H * W):
        lst[tmp + D] = lst[tmp] + calc(tmp, tmp + D)
        tmp += D

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

Submission status: Accepted

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

h,w,d = inpl()
n = h*w
di = dict()
for i in range(h):
    x = inpl()
    for j in range(w):
        di[x[j]-1] = (i,j)
a = []
for i in range(d):
    tmp = [0]
    for j in range(i,n,d):
        if j == i:
            px,py = di[j]
            continue
        nx,ny = di[j]
        tmp.append(abs(nx-px)+abs(ny-py))
        px,py = nx,ny
    a.append(list(itertools.accumulate(tmp)))

q = inp()
for _ in range(q):
    l,r = inpl()
    l,r = l-1, r-1
    now = l%d
    print(a[now][(r-now)//d] - a[now][(l-now)//d])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    h,w,d=map(int,readline().split())
    a=[list(map(int,readline().split())) for _ in range(h)]
    q=int(readline())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,readline().split())

    #座標メモ
    co=dict()
    for i in range(h):
        for j in range(w):
            co[a[i][j]]=(i,j)

    #累積和
    s=[0]*(h*w+1)
    for i in range(1,d+1):
        j=i+d
        while j<=h*w:
            distance=abs(co[i][0]-co[j][0])+abs(co[i][1]-co[j][1])
            s[j]+=s[i]+distance
            i+=d
            j+=d

    #実技試験
    for i in range(q):
        print(s[r[i]]-s[l[i]])

if __name__=="__main__":
    main()

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 = [-1]*(H*W)
y = [-1]*(H*W)

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

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

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

Q = int(input())

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

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

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

A = [list(map(int, input().split())) for _ in range(H)]
aToHW = {}
for h, row in enumerate(A):
    for w, a in enumerate(row):
        aToHW[a] = (h, w)

Q = int(input())

@lru_cache(maxsize=None)
def search(now):
    if not now + D in aToHW:
        return 0

    l, r = aToHW[now], aToHW[now + D]
    return abs(l[0] - r[0]) + abs(l[1] - r[1]) + search(now + D)

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

    ans.append(search(l) - search(r))

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,d=mp()
l=[[]for i in range(h*w+1)]
for i in range(h):
    a=lmp()
    for k in range(w):
        l[a[k]]=[i,k]
ans=[0]*(h*w+1)
for i in range(1,d+1):
    for k in range((h*w-i)//d):
        ans[i+(k+1)*d]=ans[i+k*d]+abs(l[i+k*d][0]-l[i+(k+1)*d][0])+abs(l[i+k*d][1]-l[i+(k+1)*d][1])
q=int(input())
for i in range(q):
     l,r=mp()
     print(ans[r]-ans[l])

Submission status: Accepted

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]
for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]
for i in range(h * w-d):
    num[i%d][i//d+1] = num[i%d][i//d]+abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])
q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(num[now%d-1][(goal-now%d)//d-1]-num[now%d-1][(now-now%d)//d-1])
    else:
        print(num[now%d-1][(goal-now%d)//d]-num[now%d-1][(now-now%d)//d])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, D = ZZ()
    A = [ZZ() for _ in range(H)]
    Q = Z()
    query = [ZZ() for _ in range(Q)]

    pos = [(-1, -1) for _ in range(H*W+1)]
    for i in range(H):
        for j in range(W): pos[A[i][j]] = (i, j)
    cost = [0] * (H*W+1)

    def calc(now, c):
        cost[now] = c
        if now+D > H*W: return
        x, y = pos[now]
        nx, ny = pos[now+D]
        nc = abs(nx-x) + abs(ny-y) + c
        calc(now + D, nc)

    for n in range(1, D+1): calc(n, 0)

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

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,d=mp()
l=[[]for i in range(h*w+1)]
for i in range(h):
    a=lmp()
    for k in range(w):
        l[a[k]]=[i,k]
ans=[0]*(h*w+1)
for i in range(1,d+1):
    for k in range((h*w-i)//d):
        ans[i+(k+1)*d]=ans[i+k*d]+abs(l[i+k*d][0]-l[i+(k+1)*d][0])+abs(l[i+k*d][1]-l[i+(k+1)*d][1])
q=int(input())
for i in range(q):
     l,r=mp()
     print(ans[r]-ans[l])

Submission status: Accepted

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

def calcdist(i,j):
  return abs(place[i][0]-place[j][0])+abs(place[i][1]-place[j][1])

dp=[[0] for i in range(d+1)]
for i in range(1,d+1):
  for j in range(i+d,h*w+1,d):
    dp[i].append(dp[i][-1]+calcdist(j-d,j))
    
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  i=l%d
  if i==0:
    i=d
  l=(l-1)//d
  r=(r-1)//d
  print(dp[i][r]-dp[i][l])

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def make_chain(res, seq):
        num = res
        prev = number_to_point[num]
        num += d
        while num < h * w:
            current = number_to_point[num]
            dist = abs(current[0] - prev[0]) + abs(current[1] - prev[1])
            seq.append(dist)
            num += d
            prev = current
            

    
    h, w, d = mi()
    grid = [lmi_0() for _ in range(h)]    # 0 to h*w-1
    q = ii()
    query = [lmi_0() for _ in range(q)]

    number_to_point = dict()
    for i in range(h):
        for j in range(w):
            number_to_point[grid[i][j]] = (i, j)

    chain = [[0] for _ in range(d)]    # chain[i] = (num%d == i なる数字について順にジャンプしていく時のコスト)
    for i in range(d):
        make_chain(i, chain[i])
    
    # print(chain)
    
    accum_chain = [list(accumulate(elm)) for elm in chain]

    for l, r in query:
        assert (l % d == r % d)
        res = l % d
        a = l // d
        b = r // d
        print(accum_chain[res][b] - accum_chain[res][a])




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

MAXH = 300
MAXW = 300

pos = [[] for _ in range(MAXH*MAXW+10)]
for i in range(h):
    for j in range(w):
        s = a[i][j]
        pos[s] = [i, j]

score = [0 for _ in range(MAXH*MAXW+10)]
for i in range(1, d+1):
    n = i
    while n+d <= h*w:
        x, y = pos[n]
        nx, ny = pos[n+d]
        score[n+d] += score[n]+abs(nx-x)+abs(ny-y)
        n += d

for loop in range(q):
    l, r = query[loop]
    print(score[r]-score[l])

Submission status: Accepted

Solution code:
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  #num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + (abs(num[i][0]-num[i-D][0])+ abs(num[i][1]-num[i-D][1]))
  Q = int(input())
  ans = []
  for i in range(Q):
    L, R = map(int, input().split())
    ans.append(num_sum[R-1]-num_sum[L-1])
  print(*ans, sep='\n')
if __name__ == "__main__":
  main()

Submission status: Accepted

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

a_to_ij = {}
for i, aa in enumerate(A):
  for j, a in enumerate(aa):
    a_to_ij[a] = (i, j)

cost = {}
def calc_cost(s):
  global cost
  t = s
  pre_i, pre_j = a_to_ij[s]
  c = cost[s] = 0
  while t + D <= M:
    t += D
    i, j = a_to_ij[t]
    c += abs(i-pre_i) + abs(j-pre_j)
    cost[t] = c
    pre_i, pre_j = i, j

for n in range(1, D+1):
  calc_cost(n)

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

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

Submission status: Accepted

Solution code:
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  #num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[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(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()

Submission status: Accepted

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

a_to_ij = {}
for i, aa in enumerate(A):
  for j, a in enumerate(aa):
    a_to_ij[a] = (i, j)

cost = {}
def calc_cost(s):
  global cost
  t = s
  pre_i, pre_j = a_to_ij[s]
  c = cost[(s, s)] = 0
  while t + D <= M:
    t += D
    i, j = a_to_ij[t]
    c += abs(i-pre_i) + abs(j-pre_j)
    cost[(s, t)] = c
    pre_i, pre_j = i, j

for n in range(1, D+1):
  calc_cost(n)

ans = []
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  s = L % D
  if s == 0:
    s = D
  ans.append(cost[(s, R)] - cost[(s, L)])

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
h,w,z = map(int,input().split())
a_mat = []
for i in range(h):
  a_list = list(map(int,input().split()))
  a_mat.append(a_list)
pos_dic  = {}
for i in range(h):
  for j in range(w):
    pos_dic[a_mat[i][j] - 1] = [i,j]
    
d = [0 for i in range(h*w)]
for a in range(z,h*w):
  d[a] = d[a-z] + abs(pos_dic[a][0] - pos_dic[a-z][0]) +abs(pos_dic[a][1] - pos_dic[a-z][1])
  
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  print(d[r-1] - d[l-1])

Submission status: Accepted

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

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

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

s = [[] for _ in range(D+1)]
for i in range(1,D+1):
    cost = 0
    s[i].append(0)
    for j in range(i,H*W-D+1,D):
        cost += abs(d[j][0] - d[j+D][0]) + abs(d[j][1] - d[j+D][1])
        s[i].append(cost)

Q = int(input())
for i in range(Q):
    L,R = map(int,(input().split()))
    r = L%D
    if r == 0:
        r = D
    ans = s[r][(R-r)//D]-s[r][(L-r)//D]
    print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, D = list(map(int, input().split(' ')))
    cell_list = list()
    for h in range(H):
        a_list = list(map(int, input().split(' ')))
        cell_list.extend([(a - 1, h, w) for w, a in enumerate(a_list)])
    cell_list.sort(key=lambda c: c[0])  # sort by cell number
    # calculate cumulative sum of magical power
    cumsum = dict()
    for d in range(D):
        cumsum[d] = [0]
    for x in range(D, H * W):
        d = x % D
        bef_c, c = cell_list[x - D], cell_list[x]
        m = cumsum[d][-1] + abs(c[1] - bef_c[1]) + abs(c[2] - bef_c[2])
        cumsum[d].append(m)
    # answer queries
    Q = int(input())
    queries = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(Q)]
    for L, R in queries:
        d = L % D
        print(cumsum[d][R // D] - cumsum[d][L // D])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
target = [[0,0] for _ in range(H*W+1)]
ruiseki = [[i+1] for i in range(D)]
ans = 0
for i in range(H):
    for j in range(W):
        target[grid[i][j]][0] = i+1
        target[grid[i][j]][1] = j+1
for i in range(D):
    tmp = ruiseki[i][0]
    ruiseki[i][0] = 0
    cnt = 0
    while tmp+D <= H*W:
        dist = abs(target[tmp][0]-target[tmp+D][0])+abs(target[tmp][1]-target[tmp+D][1])
        ruiseki[i].append(ruiseki[i][cnt]+dist)
        cnt += 1
        tmp += D
for i in range(Q):
    current = LR[i][0]
    tmp = D if current%D == 0 else current%D
    tmp -= 1
    print(ruiseki[tmp][((current-1)//D)+((LR[i][1]-current)//D)]-ruiseki[tmp][((current-1)//D)])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
A = [list(map(lambda s: int(s) - 1, input().split())) for i in range(H)]
Q = int(input())
queries = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(Q)]

T = {}
for i in range(H):
    for j in range(W):
        T[A[i][j]] = (i, j)
accum = [[0] for i in range(D)]
for i in range(D):
    for j in range(i + D, H * W, D):
        p = T[j - D]
        n = T[j]
        accum[i].append(accum[i][-1] + abs(p[0] - n[0]) + abs(p[1] - n[1]))

for query in queries:
    r = query[0] % D
    print(accum[r][query[1] // D] - accum[r][query[0] // D])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

p=[0]
for i in range(1,h*w+1):
    if(i-d>0):
        p.append(p[i-d]+abs(box[i][0]-box[i-d][0])+abs(box[i][1]-box[i-d][1]))
    else:
        p.append(0)

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

Submission status: Accepted

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

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

for i in range(h*w-d-1,-1,-1):
	dist[i] += dist[i+d]

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

Submission status: Accepted

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

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

for i in range(D):
    nowx,nowy=pos[i]
    idx=i
    rui=0
    pos[i]=rui
    while idx+D<H*W:
        idx+=D
        x,y=pos[idx]
        rui=rui+abs(x-nowx)+ abs(y-nowy)
        pos[idx]=rui
        nowx=x
        nowy=y

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    H, W, D = (int(i) for i in input().split())
    R = [r for r in read().rstrip().split(b'\n')]
    A = [[int(i) for i in r.split()] for r in R[:H]]

    B = [0]*(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(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

    for r in R[H+1:]:
        le, ri = (int(i) for i in r.split())
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.read
    H, W, D = (int(i) for i in input().split())
    R = [r for r in read().rstrip().split('\n')]
    A = [[int(i) for i in r.split()] for r in R[:H]]

    B = [0]*(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(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

    for r in R[H+1:]:
        le, ri = (int(i) for i in r.split())
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

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 = [0]*(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(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

h, w, d = [int(x) for x in input().split()]
n = h*w
a = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lr = [[int(x) for x in input().split()] for _ in range(q)]

from collections import defaultdict
b = defaultdict(list)
for i in range(h):
    for j in range(w):
        b[a[i][j] - 1] = [i, j]
dist = [float('inf')]*n
for i in range(d):
    dist[i] = 0
    while i + d < n:
        x1, y1 = b[i]
        x2, y2 = b[i + d]
        dist[i + d] = dist[i] + abs(x1 - x2) + abs(y1 - y2)
        i += d
for i in range(q):
    l, r = lr[i]
    l -= 1
    r -= 1
    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)]
x = [0]*(H*W+D+1)
y = [0]*(H*W+D+1)
for k in range(W):
    for l in range(H):
        x[A[l][k]] = k+1
        y[A[l][k]] = l+1

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    H,W,D=pin()
    precal_magicalresource=[]#D series
    places_num=[None]*(H*W+1)
    for h in range(1,H+1):
        temp=tupin()
        for w in range(1,W+1):
            places_num[temp[w-1]]=(h,w)
    places_num[0]=(0,0)
    #print(places_num)

    for d in range(D):#about Li%D
        d_mag=[]
        d_mag.append(0)
        temp=places_num[d]
        p=0
        while(1):
            d+=D
            if d>H*W:break
        
            s=abs(temp[0]-places_num[d][0])
            t=abs(temp[1]-places_num[d][1])
            p+=s+t
            d_mag.append((p))
            temp=places_num[d]
        precal_magicalresource.append(d_mag)
        #print(precal_magicalresource)
    Q=int(input())    
    for q in range(Q):
        l,r=pin()
        lm=l%D
        rd=r//D
        ld=l//D
        print(precal_magicalresource[lm][rd]-precal_magicalresource[lm][ld])
#%%submit!
resolve()