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: Wrong Answer

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w,d=map(int,input().split())
inds={}
for i in range(h):
    for D,j in enumerate(input().split()):
        inds[int(j)-1]=(i,D)
nows=[[0]for c in range(d)]

for k in range(d,h*w):
    a,b=inds[k]
    x,y=inds[k-d]
    k%=d
    nows[k%d].append(nows[k%d][-1]+abs(a-x)+abs(b-y))
print(nows)
q=input()
for i in inputs():
    l,r=map(int,i.split())
    l-=1;r-=1
    l,b=divmod(l,d)
    r,b=divmod(r,d)
    print(nows[b][r]-nows[b][l])

Submission status: Wrong Answer

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

from collections import defaultdict
G = defaultdict(list)
for i in range(h):
    l = list(map(int, input().split()))
    for n, item in enumerate(l):
        G[item] = [n,i]




# magic is just distance by 1

# if d is 4,
# 1,5,9 or 2,6,10.. make surplus to categorize
# query comes 10^5, so O(1) or O(logN) is limit -> cumulativesum

dp = [0 for i in range(h*w+1)]
for i in range((h*w)%d+1): # 1,2,...d
    current_place = i+1
    while current_place + d <= h*w:
        x,y = G[current_place]
        next_place = current_place + d
        x1,y1 = G[next_place]
        magic = abs(x-x1) + abs(y-y1)
        dp[next_place] = magic + dp[current_place]
        current_place = next_place

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

Submission status: Wrong Answer

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

from collections import defaultdict
G = defaultdict(list)
for i in range(h):
    l = list(map(int, input().split()))
    for n, item in enumerate(l):
        G[item] = [n,i]




# magic is just distance by 1

# if d is 4,
# 1,5,9 or 2,6,10.. make surplus to categorize
# query comes 10^5, so O(1) or O(logN) is limit -> cumulativesum

dp = [0 for i in range(h*w+1)]
for i in range((h*w)%d+1): # 1,2,...d
    current_place = i+1
    while current_place + d < h*w:
        x,y = G[current_place]
        next_place = current_place + d
        x1,y1 = G[next_place]
        magic = abs(x-x1) + abs(y-y1)
        dp[next_place] = magic + dp[current_place]
        current_place = next_place

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

Submission status: Wrong Answer

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

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    s_d[i].append(0)
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
#print(s_d)

def query(l, r):
    idx = l % d
    if idx == 0:
        idx = d
    l_d = l // d
    count = (r-l)//d
    if l_d == 0:
        cost = s_d[idx][count]
    else:
        cost = s_d[idx][l_d + count-1] - s_d[idx][l_d-1]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

Submission status: Wrong Answer

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

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    s_d[i].append(0)
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
#print(s_d)

def query(l, r):
    idx = l % d
    if idx == 0:
        idx = d
    l_d = l // d
    count = (r-l)//d
    if l_d == 0:
        l_d += 1
    cost = s_d[idx][l_d + count-1] - s_d[idx][l_d-1]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

Submission status: Wrong Answer

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

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    s_d[i].append(0)
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
#print(s_d)

def query(l, r):
    idx = l % d
    l_d = l // d
    r_d = r // d

    if idx == 0:
        idx = d
    if l_d == 0:
        l_d += 1
        r_d += 1

    cost = s_d[idx][r_d-1] - s_d[idx][l_d-1]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

Submission status: Wrong Answer

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

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    s_d[i].append(0)
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
print(s_d)

def query(l, r):
    idx = l % d
    l_d = l // d
    r_d = r // d

    if idx == 0:
        idx = d
    if l_d == 0:
        l_d += 1
        r_d += 1

    cost = s_d[idx][r_d-1] - s_d[idx][l_d-1]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

for i in range(h):
    arr[i] = list(map(int, input().split()))

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

for i in range(q):
    lr[i] = list(map(int, input().split()))


result = defaultdict(list)

for i in range(1, d + 1):
    l = i
    while l + d <= h * w:
        u = np.where(arr == l)
        v = np.where(arr == l + d)
        result[i].append(abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0]))
        l += d

ans = []
for l, r in lr:
    if l % d == 0:
        get = result[d]
        ans.append(sum(get[(l // d - 1):(r // d - 1)]))
    else:
        get = result[l]
        ans.append(sum(get[(l // d):(r // d)]))

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

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())
  u=H*W
  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      if h>u:
        break
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=l*D
    print(ans)
  return
main()

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())

  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      if h>H*W:
        break
      s=L+l*D-1
      ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      h+=l*D
    print(ans)
  return
main()

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,D=map(int,pin().split())
  d=[[]]*(H*W)
  for i in range(H):
    a=list(map(int,pin().split()))
    for j in range(W):
      d[a[j]-1]=[i,j]

  Q=int(pin())

  for k in range(Q):
    L,R=map(int,pin().split())
    t=(R-L)//D
    ans=0
    h=L
    for l in range(1,t+1):
      s=L+l*D-1
      try:
        ans+=abs(d[h-1][0]-d[s][0])+abs(d[h-1][1]-d[s][1])
      except:
        return
      h+=l*D
    print(ans)
  return
main()

Submission status: Wrong Answer

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

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

pt = [[0, 0] for _ in range(h * w + 1)]


for i in range(h):
    for j in range(w):
        pt[a[i][j]][0] = i
        pt[a[i][j]][1] = j


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

for i in range(1, h * w + 1):
    if i + d < h * w:
        x, y = pt[i+d]
        p, q = pt[i]
        c[i] = abs(x-p) + abs(y-q)


q = int(input())

for i in range(q):
    l, r = list(map(int, input().split()))
    print(sum(c[l:r:d]))

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline
read=sys.stdin.read
 
h,w,d=map(int,readline().split())
a=[list(map(int,readline().split())) for _ in range(h)]
q,*lr=map(int,read().split())

ca=dict()
for i,l in enumerate(a):
  for j,e in enumerate(l):
    ca[e]=(i+1,j+1)
mp=[[0]*((h*w)//d+1) for _ in range(d)]
for i,mpl in enumerate(mp):
  for j,_ in enumerate(l[:-1]):
    if 0<i+d*j<=h*w-d:
      mpl[j+1]+=mpl[j]+abs(ca[i+d*j][0]-ca[i+d*(j+1)][0])\
                +abs(ca[i+d*j][1]-ca[i+d*(j+1)][1])
for l,r in zip(*[iter(lr)]*2):
  print(mp[l%d][r//d]-mp[l%d][l//d])

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W,D=list(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)]


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

dict_dir = {}

for i in range(Q):
    L = LR[i][0]
    R = LR[i][1]
    useMP = 0
    if (L,R) not in dict_dir:
        point = range(L,R+1,D)
        for p in range(1,len(point)):
            x0,y0 = dict_map[point[p-1]]
            x1,y1 = dict_map[point[p]]
            useMP += abs(x0-x1)+abs(y0-y1)
            dict_dir[(point[p-1],point[p])]=abs(x0-x1)+abs(y0-y1)
            dict_dir[L,point[p]]=abs(x0-x1)+abs(y0-y1)
        dict_dir[(L,R)]=useMP
    else:
        useMP = dict_dir[(L,R)]
    print(useMP)

Submission status: Wrong Answer

Solution code:
def binary_search(func, array, left=0, right=-1):
    if right==-1:right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

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

B = []
for i in range(H):
  for j in range(W):
    B.append((A[i][j],(i,j)))

B = sorted(B)

for q in range(Q):
  l, r = lr[q]
  if l==r:
    print(0)
    continue
  ans = 0
  idx=0
  for i in range(l,r+D,D):
    idx = binary_search(lambda x:x[0]>i,B,idx)
    if i == l:
      old = B[idx][1]
      continue
    new = B[idx][1]
    diff = abs(new[0] - old[0]) + abs(new[1] - old[1])
    ans += diff
    old = new
  print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = [int(x) for x in input().strip().split()]
    M = [0] * H
    revM = {}
    for h in range(H):
        M[h] = [int(x) for x in input().strip().split()]
        for i, w in enumerate(M[h]):
            revM[w] = (h, i)
    Q = int(input())
    for q in range(Q):
        ans = 0
        l, r = [int(x) for x in input().strip().split()]
        d = D
        while l + d <= r:
            # print('d={}, revM[l]={}'.format(d, revM[l]))
            ans += abs(revM[l][0] - revM[l+d][0]) + abs(revM[l][1] - revM[l+d][1])
            revM[l], revM[l+d] = revM[l+d], revM[l]
            d += D
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

H, W, D = list(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)]

# 1 -> 1+D ->
# 2 -> 2+D ->
# 3 -> 3+D -> みたいなものを事前に計算

# 辞書で管理する
# d[A[i][j]] = [i,j] みたいな感じ
d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)

    p.append(q)


# for l, r in LR:
#     i = l % D - 1
#     s = (l + i) // D
#     e = (r + i) // D
#     print(p[i][e] - p[i][s])

Submission status: Wrong Answer

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

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

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[l:r + 1:D].sum()


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

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

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[l:r + 1 - D:D].sum()


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W, D = MAP()
A = [LIST() for _ in range(H)]
Q = INT()
LR = [LIST() for _ in range(Q)]

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

for y in range(H):
	for x in range(W):
		#print(dic)
		dic[A[y][x]%D].append([A[y][x], y, x])

for lis in dic:
	lis.sort(key = lambda x:x[0])

for lis in dic:
	lis[0][0] = 0
	for i in range(len(lis)):
		if i == len(lis)-1:
			break
		point = (lis[i][1], lis[i][2])
		dist_point = (lis[i+1][1], lis[i+1][2])
		lis[i+1][0] = lis[i][0] + abs(point[0] - dist_point[0]) + abs(point[1]-dist_point[1])

print(dic)
for L, R in LR:
	print(dic[R%D][ceil(R/D)-1][0] - dic[R%D][ceil(L/D)-1][0])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
power_acc[0].insert(0, 0)
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D-1] - power_acc[L%D][L//D-1])

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

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

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(a.index(i+1)-1, next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = dbl[i][now][0]
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

Submission status: Wrong Answer

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:
            ans += magic[R-D]
        else:
            ans += magic[R-D]-magic[L-D]
        print(ans)

Submission status: Wrong Answer

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+1)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]]=[i,j]
#print(lis)
cost=[[0]*(h*w+1) for i in range(d)]
for i in range(d):
    cost[i][i]=0
    for j in range(1,h*w):
        if i+d*j<h*w+1:
            cost[i][i+d*j]=cost[i][i+d*j-d]+abs(lis[i+d*j][0]-lis[i+d*(j-1)][0])+abs(lis[i+d*j][1]-lis[i+d*(j-1)][1])
#print(cost)
            
        
#print(cost)
q=I()
for i in range(q):
    ans=0
    l,r=MI()
    k=l%d
    print(cost[k][r]-cost[k][l])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  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

#####MakeDivisors######
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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W,D = IL()
posx = [None for i in range(H*W)]
posy = [None for i in range(H*W)]

for i in range(H):
  L = IL()
  for j in range(W):
    posx[L[j]-1] = i
    posy[L[j]-1] = j
    
DICX = DD(lambda : [0])
DICY = DD(lambda : [0])

for x in range(D,H*W):
  i = x%D
  DICX[i].append(DICX[i][-1]+abs(posx[x]-posx[x-D]))
  DICY[i].append(DICX[i][-1]+abs(posy[x]-posy[x-D]))
  
Q = I()
for _ in range(Q):
  L,R = IL()
  L,R = L-1,R-1
  i = L%D
  s = L//D
  t = R//D
  print((DICX[i][t]-DICX[i][s])+(DICY[i][t]-DICY[i][s]))

Submission status: Wrong Answer

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

H, W, D = map(int, input().split())
MAX = H * W + 1

d = [0] * (MAX + 1)
px = [None] * (MAX + 1)
py = [None] * (MAX + 1)

for h in range(H):
    Ah = list(map(int, input().split()))
    for w in range(W):
        px[Ah[w]] = h
        py[Ah[w]] = w

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
h,w,d= map(int, input().split())
a = {}
for y in range(h):
    line = list(map(int, input().split()))
    for x in range(len(line)):
        a[line[x]-1] = (y,x)

# 問題の考え方
# DP的な感じで解ける
# まずGridになっているが、1次元の配列として考える 3*3(=9マスある状態) なら
#   1,2,3,4,5,6,7,8,9
# このときに数値の低い方から高い方へいくとゴールにつく(Ri-LiがDの倍数であること)が保証されるので最後の数字へ向かうときにかかるコストを考える(以下、3*3の例)
#   D=2としたときに、9はこれ以上進めないので、コスト0, 8もそれ以上進めないので コスト0, 7は9に行けるので9のコスト+7から9へ向かうコストで算出可能
#   また、5~9へのコストは1~9へのコスト引く1~5までのコストとなるので累積和的に答えを算出することが可能

num = len(a)
dp = [0]*num
for i in range(num-1, -1, -1):
    print(i)
    if i+d <= num-1:
        x, y = a[i]
        px, py = a[i+d]
        dp[i] = dp[i+d] + abs(x-px) + abs(y-py)

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