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: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<H*W
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D**2<H*W
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<100
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(D+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,D+1):
  for j in range(1,H*W//D+1):
    if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
g[0]=g[D]
for q in range(Q):
  l,r=map(int,input().split());t=l%D;print(g[t][r]-g[t][l])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(H*W,0,-1):
  if i+D<=H*W:g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
  for j in range(H*W//D,1,-1):
    if i+D*j<=H*W:g[i][i+D*j]=g[i+D][i+D*j]+g[i][i+D]
for q in range(Q):
  l,r=map(int,input().split());print(g[l][r])

Submission status: Time Limit Exceeded

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

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

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

MAX_LOG = math.ceil(math.log2(h*w))
# MAX_LOG = 18
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


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

Submission status: Time Limit Exceeded

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

def dist(p1, p2):
    return abs(a[p1][0] - a[p2][0]) + abs(a[p1][1] - a[p2][1])

MAX_LOG = math.ceil(math.log2(h*w))
b = [[0 for j in range(MAX_LOG)] for i in range(h*w+1)]
for j in range(MAX_LOG):
    for i in range(1, h*w+1):
        if j == 0:
            if i + d < h*w + 1:
                b[i][j] = dist(i, i + d)
        elif i + d*(1<<j) < h*w + 1:
            b[i][j] = b[i][j-1] + b[i + d*(1<<(j-1))][j-1]

# for bi in b:
#     print(bi)

def query(l, bit):
    if bit == 0:
        return 0
    j = 0
    while (bit>>j) & 1 == 0:
        j += 1

    return b[l][j] + query(l + d * (1<<j), bit ^ (1<<j))


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

Submission status: Time Limit Exceeded

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


numlist = [[0,0]] * (H*W+1)
for i in range(H):
    for j in range(W):
        numlist[A[i][j]] = [i,j]

'''
ruisekiwa = [0] * (H*W+1)
tmp = 0
x,y = numlist[1]

for i in range(2,H*W+1):
    x2,y2 = numlist[i]
    tmp += abs(x-x2)+abs(y-y2)
    x,y = x2,y2
    ruisekiwa[i] = tmp
'''  

for i in range(Q):
    ans = 0
    start,goal = LR[i]
    x,y = numlist[start]
    xg,yg = numlist[goal]
    now = start
    while now != goal:
        now += D
        xn,yn = numlist[now]
        ans += abs(x-xn) + abs(y-yn)
        x,y = xn,yn
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  for i in range(q):
    l,r = (int(m) for m in input().split())
    if l == r:
      print(0)
    else:
      ans = 0
      for j in range((r-l)//d):
        leftx,lefty = query[(l-1)+j*d]
        rightx,righty = query[(l-1)+(j+1)*d]
        ans += abs(rightx-leftx)+abs(righty-lefty)
      print(ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:

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

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())


for i in range(Q):

    ans = 0

    L,R = map(int,input().split())

    now = dic[L]

    for j in range((R-L) // D):

        now = dic[L + j * D]
        nex = dic[L + (j+1) * D]

        ans += abs(now[0]-nex[0]) + abs(now[1]-nex[1])

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import *
from functools import lru_cache

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

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    (h,), (w,) = where(A==i+1)
    dp[i] = (h, w)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        distance[i] = 0
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])

Submission status: Time Limit Exceeded

Solution code:
from numpy import *
from functools import lru_cache

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

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    (h,), (w,) = where(A==i+1)
    dp[i] = (h, w)

@lru_cache(H*W)
def f(p, q) :
    x, y = dp[p-1]
    i, j = dp[q-1]
    return abs(x-i)+abs(y-j)

for l, r in LR :
    print(sum([f(p, p+D) for p in range(l, r, D)], dtype=int))

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(H*W)]
for i in range(H*W) :
    for h, l in enumerate(A) :
        try :
            w = l.index(i+1)
            break
        except ValueError:
            pass
    dp[i] = (h, w)

def f(p, q) :
    x, y = dp[p-1]
    i, j = dp[q-1]
    return abs(x-i)+abs(y-j)

for l, r in LR :
    print(sum(f(p, p+D) for p in range(l, r, D)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import numpy as np

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

@lru_cache(300**4)
def f(p, q) :
    (x,), (y,) = np.where(A==p)
    (i,), (j,) = np.where(A==q)
    return abs(x-i)+abs(y-j)

for l, r in LR :
    print(sum(f(p, p+D) for p in range(l, r, D)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
    
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)
#print(A_dict)

N = H*W+1
edges = []

for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    edges.append((s,g,cost))

from collections import defaultdict
graph = defaultdict(lambda:{})
for x,y,z in edges:
    graph[x][y] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０
    
from heapq import heappush, heappop    
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

dist = {}
for i in range(1, D+1):
    dist[i] = dijkstra(graph, i, N)
#print(dist)
for l, r in LR:
    idx = r%D
    if idx == 0:
        idx = D
    print(dist[idx][r]-dist[idx][l])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
    
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)
#print(A_dict)

N = H*W+1
edges = []
graph = [[float("inf") for i in range(N)] for i in range(N)] 
for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    edges.append((s,g,cost))
for x,y,z in edges:
    graph[x][y] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０
    
from collections import defaultdict
dist = defaultdict(lambda: {})

for i in range(1, N):
    dist[i][i] = 0
    d = 0
    s = i
    g = i+D
    while g < N:
        dist[i][g] = dist[i][s]+graph[s][g]
        s = g
        g = s+D
#print(dist)
for l, r in LR:
    print(dist[l][r])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
    
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)
#print(A_dict)
    
def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

N = H*W+1
graph = [[float("inf") for i in range(N)] for i in range(N)] 
edges = []

for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    edges.append((s,g,cost))

for x,y,z in edges:
    graph[x][y] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０
shortest = warshall_floyd(graph, N)

for l, r in LR:
    print(shortest[l][r])

Submission status: Time Limit Exceeded

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

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

    for R, L in queries:
        i, j = d[R]
        magic = 0
        if R != L:
            while R+D != L:
                k, l = d[R+D]
                magic += abs(i-k)+abs(j-l)
                i, j = k, l
                R = R+D
            k, l = d[R+D]
            magic += abs(i-k) + abs(j-l)
        print(magic)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d):
    for j in range(i + d, (h * w), d):
        if j > 0:
            accum_list[i] += abs(num_dict[j][0] - num_dict[j - d][0]) + abs(num_dict[j][1] - num_dict[j - d][1])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
num_dict = {}
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num] = (i + 1, j + 1)
q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r + d, d):
        n_x, n_y = num_dict[i]
        if i > l:
            ans += abs(temp_x - n_x) + abs(temp_y - n_y)
        temp_x = n_x
        temp_y = n_y
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
b = [list(map(int,input().split())) for _ in range(q)]
p =[0]*h*w
    
for i in range(h):
    for j in range(w):
        tmp = a[i][j]
        p[tmp-1] = [i,j]

def power(x,y):
    return abs(p[x-1][0]-p[y-1][0])+abs(p[x-1][1]-p[y-1][1])

for k in range(q):
    ans = 0
    l = b[k][0]
    r = b[k][1]
    while l < r:
        ans += power(l,l+d)
        l += d
    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        A[row[j]] = [i+1, j+1]

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    ans = 0
    while L != R:
        ans += abs(A[L+D][0] - A[L][0]) + abs(A[L+D][1] - A[L][1])
        L += D
    print(ans)

Submission status: Time Limit Exceeded

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

A = [[]]*(H*W+1)
for i in range(H):
  a = list(map(int,input().split()))
  for j in range(W):
    A[a[j]] = [i, j]

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

def magic(LR):
  magic = 0
  for i in range(int((LR[1]-LR[0])/D)):
    magicx = abs(A[LR[0]+i*D][0] - A[LR[0]+(i+1)*D][0]) 
    magicy = abs(A[LR[0]+i*D][1] - A[LR[0]+(i+1)*D][1]) 
    magic += magicx + magicy
  return magic

for i in range(Q):
  if (LR[i][0] == LR[i][1]):
    print(0)
  else:
    print(magic(LR[i]))

Submission status: Time Limit Exceeded

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

def find(n):
  for i in range(len(A)):
    if n in A[i]:
      return [i, A[i].index(n)]

def magic(LR):
  magic = 0
  for i in range(int((LR[1]-LR[0])/D)):
    start = find(LR[0]+i*D)
    goal = find((LR[0]+(i+1)*D))
    magic += (abs(start[0]-goal[0]) + abs(start[1]-goal[1]))
  return magic
  
for i in range(len(LR)):
  if (LR[i][0] == LR[i][1]):
    print(0)
  else:
    print(magic(LR[i]))

Submission status: Time Limit Exceeded

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

pos = [0]*(H*W)
for j in range(H):
  A = list(map(int,input().split()))
  for i in range(W):
    pos[A[i]-1] = (i,j)
#print(link)

memo = [0]*(H*W)
for x0 in range(H*W):
  for x in range(x0+D,H*W,D):
    i,j = pos[x-D][0],pos[x-D][1]
    u,v = pos[x  ][0],pos[x  ][1]
    memo[x] = memo[x-D]+abs(i-u)+abs(j-v)

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

Submission status: Time Limit Exceeded

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

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(q):
    s=0
    for j in range(l[i]+d-1,r[i],d):
        s+=abs(ans[j][0]-ans[j-d][0])+abs(ans[j][1]-ans[j-d][1])
    print(s)

Submission status: Time Limit Exceeded

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

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Submission status: Time Limit Exceeded

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

    h,w,d=map(int,input().split())
    A=[]
    for i in range(h):
        l=list(map(int,input().split()))
        for j in range(w):
            A.append([l[j],i,j])
    ans=[]
    for i in sorted(A):
        ans.append(i[1:])
    q=int(input())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,input().split())
    for i in range(h*w-1,d-1,-1):
        ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
    for i in range(d):
        ans[i]=0
    for i in range(q):
        print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))
sol()

Submission status: Time Limit Exceeded

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

h,w,d=map(int,input().split())
A=[]
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A.append([l[j],i,j])
ans=[]
for i in sorted(A):
    ans.append(i[1:])
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

h,w,d=map(int,input().split())
a=[list(map(int,input().split())) for _ in [0]*h]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
A=[]
for i in range(h):
    for j in range(w):
        heappush(A,[a[i][j],i,j])
ans=[]
for i in range(h*w):
    ans.append(heappop(A)[1:])
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Submission status: Time Limit Exceeded

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

link = [0]*(H*W)
for j in range(H):
  A = list(map(int,input().split()))
  for i in range(W):
    link[A[i]-1] = (i,j)
#print(link)

Q = int(input())
for _ in range(Q):
  L,R = map(int,input().split())
  L -= 1
  R -= 1
  #print(L,R)
  
  ans = 0
  for x in range(L+D,R+1,D):
    i,j = link[x-D][0],link[x-D][1]
    u,v = link[x  ][0],link[x  ][1]
    #print(i,j,u,v)
    ans += abs(i-u)+abs(j-v)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for index in range(L//D+1, R//D+1):
        # for position in mod_array[L%D][L//D+1:R//D+1]:
            position = mod_array[L%D][index]
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for position in mod_array[L%D][L//D+1:R//D+1]:
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for position in mod_array[L%D][L//D+1:R//D+1]:
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        


main()

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# print(amaris[:10])

Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    coords = amaris[m][s:g+1]
    ans = 0
    x_pre,y_pre = coords[0]
    for x, y in coords[1:]:
        ans += abs(x-x_pre)+abs(y-y_pre)        
        x_pre = x
        y_pre = y
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
numlist = []
for i in range(h * w):
  numlist.append([])

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

for k in range(q):
  mp = 0
  l, r = map(int, input().split())
  for n in range(l, r, d):
    mp += abs(numlist[n-1][0] - numlist[n+d-1][0]) + abs(numlist[n-1][1] - numlist[n+d-1][1])
  print(mp)

Submission status: Time Limit Exceeded

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

for k in range(q):
  mp = 0
  l, r = map(int, input().split())
  for n in range(l, r, d):
    mp += abs(numlist[n-1][0] - numlist[n+d-1][0]) + abs(numlist[n-1][1] - numlist[n+d-1][1])
  print(mp)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
d = dict()
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]
for L, R in LR:
    pow = 0
    while L != R:
        i, j = d[L]
        L += D
        x, y = d[L]
        pow += abs(x - i) + abs(y - j)
    print(pow)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i,j]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    for i in range(x,y-1,d):
        ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i,j]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    try:
        for i in range(x,y-1,d):
            ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
        print(ans)
    except:print(0)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i+1,j+1]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    try:
        for i in range(x,y-1,d):
            ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
        print(ans)
    except:print(0)

Submission status: Time Limit Exceeded

Solution code:
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i+1,j+1]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
for x,y in order:
    ans=0
    if x-y==0:print(0);continue
    try:
        for i in range(x,y-1,d):
            ans +=abs(adress[i+d][0]-adress[i][0])+abs(adress[i+d][1]-adress[i][1])
        print(ans)
    except:print(0)