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 = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
L = []
R = []
for i in range(Q):
    temp = list(map(int, input().split()))
    L.append(temp[0])
    R.append(temp[1])


def findNumber(num):
    for h in range(H):
        if num in A[h]:
            w = A[h].index(num)
            return [h, w]


for q in range(Q):
    pos = [findNumber(i) for i in list(range(L[q], R[q] + 1))[::D]]
    cost = sum([sum([abs(pos[i][j] - pos[i + 1][j]) for j in range(2)]) for i in range(len(pos) - 1)])
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]
times = int(input())
for i in range(0, times):
    temp = list(map(int, input().split(" ")))
    nowloc = temp[0]
    ans = 0
    while nowloc != temp[1]:
        ans += abs(data[nowloc][0] - data[nowloc + a[2]][0]) + abs(data[nowloc][1] - data[nowloc + a[2]][1])
        nowloc += a[2]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(i) for i in input().split(" ")]
A = [[int(i) for i in input().split(" ")] for j in range(H)]
dic_a = {}
for i in A:
    for j in i:
       dic_a[j] = (A.index(i), i.index(j))
Q = int(input())
LR = [[int(i) for i in input().split(" ")] for j in range(Q)]

maryoku_list = []
for q in range(Q):
    maryoku = 0
    x = LR[q][0]
    while(True):
        if(x == LR[q][1]):
            maryoku_list.append(maryoku)
            break
        else:
            _x, _y = dic_a[x]
            x += D
            i, j = dic_a[x]
            maryoku += abs(_x - i) + abs(_y - j)
for i in maryoku_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)


q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = 0
    while l!=r:
        c1 = table[l]
        c2 = table[l+d]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
        l += d
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def solve(numbers, queries, D):
    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            sx, sy = numbers[l]
            gx, gy = numbers[l+D]
            ans += abs(sx - gx) + abs(sy - gy)
            l += D
        print(ans)


def main(args):
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    numbers = dict()
    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, D)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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


def findNumber(num):
    for h in range(H):
        if num in A[h]:
            w = A[h].index(num)
            return [h, w]


for q in range(Q):
    pos = []
    for i in list(range(L[q], R[q] + 1))[::D]:
        pos.append(findNumber(i))
    cost = 0
    for i in range(len(pos) - 1):
        cost += sum([abs(pos[i][j] - pos[i + 1][j]) for j in range(2)])
    print(cost)

Submission status: Time Limit Exceeded

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

mp = []

for a in range(h):
  mp += map(int,raw_input().split(" "))

data = [-1] * (h*w + 1)

for a in range(d+1,h*w+1):
  l = mp.index(a-d)
  r = mp.index(a)
  x = abs((r/w) - (l/w))
  y = abs((r%w) - (l%w))
  data[a] = x+y

data2 = [-1] * (h*w + 1)

for a in range(d+1,h*w+1):
  if a - d <= 0:
    continue
  data2[a] = data2[a-d] + data[a]

q = int(raw_input())

for a in range(q):
  l,r = map(int,raw_input().split(" "))
  print data2[r] - data2[l]

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0

@lru_cache(maxsize=None)
def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now+d
        next = now + d
        prevy, prevx = pos[now-1][1], pos[now-1][2]
        nexty, nextx = pos[next-1][1], pos[next-1][2]
        ans += (abs(nexty - prevy) + abs(nextx - prevx))
    return ans

for pr, ne in way:
    print(solve(pr, ne))

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split(' '))
matrix = [list(map(int, input().split(' '))) for _ in range(h)]
map2 = {}
for i in range(h):
    for j in range(w):
        map2[matrix[i][j]] = [i, j]
        
q = int(input())
lr = [list(map(int, input().split(' '))) for _ in range(q)]


for l, r in lr:
    cnt = 0
    x, y = map2[l]
                
    while l != r:
        l = l + d
        i, j = map2[l]
        cnt += abs(x - i) + abs(y - j)
        x = i
        y = j
                    
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w, D = map(int, raw_input().split())

d = dict()
for i in xrange(h):
    j = 0
    for n in map(int, raw_input().split()):
        d[n] = (i+1, j+1)
        j += 1

for i in xrange(input()):
    l, r = map(int, raw_input().split())
    ans = 0
    px, py = d[l]
    while l <= r:
        x, y = d[l]
        ans += abs(px-x)+abs(py-y)
        px = x
        py = y
        l += D
    print ans

Submission status: Time Limit Exceeded

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

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        p1 = pos[x]
        p2 = pos[y]
        result += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x += D
    print(result)

Submission status: Time Limit Exceeded

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]
times = int(input())
for i in range(0, times):
    line = input().split(" ")
    temp = list(map(int, line))
    nowloc = temp[0]
    ans = 0
    while nowloc != temp[1]:
        ans += abs(data[nowloc][0] - data[nowloc + a[2]][0]) + abs(data[nowloc][1] - data[nowloc + a[2]][1])
        nowloc += a[2]
    print(ans)

Submission status: Time Limit Exceeded

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

rec = {}


def cal(L, R):
    if (L, R) in rec:
        return rec[(L, R)]
    else:
        p = abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        rec[(L, R)] = cal(L + D, R) + p
        return rec[(L, R)]


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

Submission status: Time Limit Exceeded

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


for l, r in lr:
    cnt = 0
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == l:
                x = i
                y = j
                
    while l != r:
        l = l + d
        for i in range(h):
            for j in range(w):
                if matrix[i][j] == l:
                    cnt += abs(x - i) + abs(y - j)
                    x = i
                    y = j
                    
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

H, W, D = map(int,input().split())
dist = [[float("inf") for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(H*W+1):
  dist[i][i] = 0
#dist[i][j]は隣接行列
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i][i+D] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
#print(dist)
dist = Warshall_Floyd(dist,H*W+1)
#print(dist)
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  print(dist[L][R])

Submission status: Time Limit Exceeded

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

mp = []

for a in range(h):
  mp += map(int,raw_input().split(" "))

data = [-1] * (h*w + 1)

for a in range(d+1,h*w+1):
  l = mp.index(a-d)
  r = mp.index(a)
  x = abs((r/w) - (l/w))
  y = abs((r%w) - (l%w))
  data[a] = x+y

q = int(raw_input())

for a in range(q):
  l,r = map(int,raw_input().split(" "))
  ans = 0
  for b in range(l+d,r+1,d):
    ans += data[b]
  print ans

Submission status: Time Limit Exceeded

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

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    for L, R in Qs:
        power = 0
        while L != R:
            i, j = np.where(board == L)
            L += D
            x, y = np.where(board == L)
            power += int(abs(x-i) + abs(y-j))
        print(power)

Submission status: Time Limit Exceeded

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

def find(A, x):
    for i, row in enumerate(A):
        if x in row:
            return row.index(x), i
    return -1, -1

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        p1 = find(A, x)
        p2 = find(A, y)
        result += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x += D
    print(result)

Submission status: Time Limit Exceeded

Solution code:
h, w, D = map(int, raw_input().split())

m = list()
for i in xrange(h):
    m.append(map(int, raw_input().split()))
d = dict()
for i in xrange(h):
    for j in xrange(w):
        d[m[i][j]] = (i+1, j+1)

for i in xrange(input()):
    l, r = map(int, raw_input().split())
    ans = 0
    px, py = d[l]
    while l <= r:
        x, y = d[l]
        ans += abs(px-x)+abs(py-y)
        px = x
        py = y
        l += D
    print ans

Submission status: Time Limit Exceeded

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

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

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

Q = int(input())

def solve(l, r):
    ans = 0
    while l != r:
        x,y = A[l-1]
        x2,y2 = A[l+D-1]
        ans += abs(x-x2) + abs(y-y2)
        l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(solve(L, R))
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))

Submission status: Time Limit Exceeded

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

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

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

Q = int(input())

def solve(l, r):
    ans = 0
    while l != r:
        x,y = A[l-1]
        x2,y2 = A[l+D-1]
        ans += abs(x-x2) + abs(y-y2)
        l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    lrs.append((L,R))

for info in lrs:
    L,R = info
    print(solve(L, R))

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = []
C = [0 for _ in range(H * W + 1)]
for h in range(H):
    A.append(list(map(int, input().split())))
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
Q = int(input())
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    p = (C[l][0], C[l][1])
    l += D
    while l <= r:
        n = (C[l][0], C[l][1])
        ans += abs(n[0] - p[0]) + abs(n[1] - p[1])
        p = n
        l += D
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    ans = 0
    l -= 1
    r -= 1
    i, j = c_map[l]
    while l != r:
        i2, j2 = c_map[l + d]
        ans += abs(i - i2) + abs(j - j2)
        l += d
        i, j = i2, j2
    buf.append(ans)

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

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(_) for _ in raw_input().split()]
mi = [None] * (h * w + 1)
for i in range(h):
  for j, v in enumerate(int(_) for _ in raw_input().split()):
  	mi[v] = (i, j)

q = int(raw_input())
for _ in range(q):
  l, r = [int(__) for __ in raw_input().split()]
  ans = 0
  for l0 in range(l, r, d):
    r0 = l0 + d
    lx, ly = mi[l0]
    rx, ry = mi[r0]
    ans += abs(rx - lx) + abs(ry - ly)

  print(ans)

Submission status: Time Limit Exceeded

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

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

buf = []
for l, r in queries:
    ans = 0
    l -= 1
    r -= 1
    i, j = c_map[l]
    while l != r:
        i2, j2 = c_map[l + d]
        ans += abs(i - i2) + abs(j - j2)
        l += d
        i, j = i2, j2
    buf.append(ans)

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

Submission status: Time Limit Exceeded

Solution code:
h, w, d = [int(_) for _ in raw_input().split()]
m = [[int(_) for _ in raw_input().split()] for __ in range(h)]
mi = {
  m[i][j]: (i, j)
  for i in range(h)
  for j in range(w)
}
q = int(raw_input())
for _ in range(q):
  l, r = [int(__) for __ in raw_input().split()]
  ans = 0
  for l0 in range(l, r, d):
    r0 = l0 + d
    lx, ly = mi[l0]
    rx, ry = mi[r0]
    ans += abs(rx - lx) + abs(ry - ly)

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,d = LI()
    a = [LI() for _ in range(h)]
    q = I()
    lr = [LI() for _ in range(q)]
    t = {}
    for i in range(h):
        for j in range(w):
            t[a[i][j]] = (i,j)

    m = {}
    def f(l,r):
        if l == r:
            return 0
        k = (l,r)
        if k in m:
            return m[k]
        res = abs(t[l][0]-t[l+d][0]) + abs(t[l][1]-t[l+d][1])
        res += f(l+d,r)
        m[k] = res
        return res
    rr = []
    for l,r in lr:
        rr.append(f(l,r))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

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].append(nows[k][-1]+abs(a-x)+abs(b-y))
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: Accepted

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(d): # 0,1,2,...d-1
    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: Accepted

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
b = [0]*(h*w+1)
for i in range(h):
  for j in range(w):
    b[a[i][j]] = (i,j)
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
  c[i] = c[i-d] + abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
for l,r in lr:
  print(c[r]-c[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+1)
p = [[] for _ in range(H*W+1)]

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

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

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

Submission status: Accepted

Solution code:
def main():
    H,W,D = map(int,input().split())
    N = H*W
    A = []
    for i in range(H):
        A.append(list(map(int, input().split())))
    places = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            places[A[i][j]] = (i,j)
    dp = [0] * (N+1)
    for i in range(D+1,N+1):
        y1,x1 = places[i-D]
        y2,x2 = places[i]
        dp[i] = dp[i-D]+abs(x1-x2)+abs(y1-y2)
    

    Q = int(input())
    queries = []
    ans = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans.append(dp[r] - dp[l])
    print('\n'.join(map(str,ans)))
main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    H, W, D = mapline()
    A = [[-1] * (W+1) for _ in range(H+1)]
    for i in range(1, H+1):
        A[i][1:] = mapline()

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

    cache = [-1] * (H*W+1)

    Q = intread()
    for _ in range(Q):
        l, r = mapline()
        if cache[r] == -1:
            mostR = r + (H*W - r) // D * D
            mostL = l % D
            if not mostL:
                mostL = D
            ci, cj = V[mostR]
            tmp = 0
            cache[mostR] = 0
            #print(mostL, mostR)
            for v in range(mostR - D, mostL-D, -D):
                #print(v, V[v])
                ni, nj = V[v]
                tmp += abs(ni - ci) + abs(nj - cj)
                cache[v] = tmp
                ci, cj = ni, nj
        #print(cache)
        print(cache[l] - cache[r])


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Accepted

Solution code:
def main():
    h,w,d = map(int,input().split())
    a = []
    for i in range(h):
        a.append(list(map(int,input().split())))
    M = [[] for i in range(h*w)]
    for i in range(h):
        for j in range(w):
            M[a[i][j]-1] = [i,j]
    dist = [0 for i in range(h*w)]
    for i in range(h*w):
        if i-d>=0:
            dist[i] += dist[i-d] + abs(M[i][0]-M[i-d][0]) + abs(M[i][1]-M[i-d][1])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def main():
    H, W, D = map(int, input().split())
    coordinate = [None] * (H*W)
    for i in range(H):
        for j, A in enumerate(list(map(int, input().split()))):
            coordinate[A-1] = (i, j)
    
    cost = [0] * (H*W)
    dist = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1])
    for i in range(D, H*W):
        u,v = divmod(i, D)
        cost[i] = cost[i-D] + dist(coordinate[i], coordinate[i-D])

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

main()

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
ans=[0 for _ in range(h*w+1)]
za=[[] for _ in range(h*w+1)]
for i in range(h):
  a=list(map(int,input().split()))
  for x in range(w):
    za[a[x]].append(i)
    za[a[x]].append(x)
  

for x in range(1,h*w+1):
  if x+d<=w*h:
    ans[x+d]=ans[x]+abs(za[x+d][0]-za[x][0])+abs(za[x+d][1]-za[x][1])
    
q=int(input())
for _ in range(q):
  e,f=map(int,input().split())
  print(ans[f]-ans[e])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

dp = [0 for _ in range(H*W+1)]

for i in range(1, D+1):
    dp[i] = 0

for i in range(D+1, H*W+1):
    ni, nj = d[i]
    pi, pj = d[i - D]
    dp[i] = dp[i - D] + abs(ni - pi) + abs(nj - pj)

for i in range(Q):
    ans = 0
    l, r = na()
    ans = dp[r] - dp[l]
    print(ans)

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
T = []
P = {}
for i in range(H):
    A = list(map(int, input().split()))
    T.append(A)
Q = int(input())
for i in range(H):
    for j in range(W):
        P[T[i][j]] = [i, j]

Jump = [[0] for _ in range(D+1)]
for i in range(1, D+1):
    total = 0
    for j in range(i, H*W+1-D, D):
        total += abs(P[j+D][0] - P[j][0]) + abs(P[j+D][1] - P[j][1])
        Jump[i].append(total)
Ans = []
for i in range(Q):
    L, R = map(int, input().split())
    k = L % D
    start = L//D
    end = R//D
    if k == 0:
        k += D
        start -= 1
        end -= 1
    Ans.append(Jump[k][end] - Jump[k][start])

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

Submission status: Accepted

Solution code:
H, W, D = map(int,input().split())
d = {}
for i in range(1, H+1):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i, j+1)
acc = [[] for _ in range(D)]
for i in range(1, D+1):
    acc[i-1].append(0)
    for j in range(i, H*W+1-D, D):
        x,y = d[j]
        a,b = d[j+D]
        #print("po:",j, j+D)
        acc[i-1].append(acc[i-1][-1]+abs(a-x)+abs(b-y))
    
Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    print(acc[(l-1)%D][(r-1)//D]-acc[(l-1)%D][(l-1)//D])

Submission status: Accepted

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): # i:= スタート位置　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 # スタート位置 = idx　
    if idx == 0:
        idx = d
    # s_d[idx]の配列を使用
    # l, rをs_d[idx]上のインデックスに合わせる
    l_d = l // d
    r_d = r // d
    if l % d == 0:
        l_d -= 1
        r_d -= 1
    cost = s_d[idx][r_d] - s_d[idx][l_d]
    return cost


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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
arys=[[] for i in range(d)]
sumarys=[[0] for i in range(d)]
biarys=[[] for i in range(d)]
for i in range(h):
  for j in range(w):
    x=a[i][j]%d
    arys[x].append((a[i][j],i,j))
for i in range(d):
  arys[i].sort(key=lambda x:x[0])
  tmp=0
  y,pi,pj=arys[i][0]
  biarys[i].append(y)
  for j in range(1,len(arys[i])):
    y,ni,nj=arys[i][j]
    biarys[i].append(y)
    tmp+=abs(pi-ni)+abs(pj-nj)
    sumarys[i].append(tmp)
    pi,pj=ni,nj
from bisect import bisect_left
for l,r in lr:
  x=l%d
  li=bisect_left(biarys[x],l)
  ri=bisect_left(biarys[x],r)
  print(sumarys[x][ri]-sumarys[x][li])

Submission status: Accepted

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

dst=[0 for i in range(d)]
for i in range(d,n):
  dst.append(abs(a[i-d][0]-a[i][0])+abs(a[i-d][1]-a[i][1]))

s=[0 for i in range(d)]
for i in range(d,n):
  s.append(s[i-d]+dst[i])

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

Submission status: Accepted

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

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

index = [-1]*(h*w)
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(len(a)):
        index[a[j]-1] = (i+1, j+1)
        # index[a[j]-1] = (i, j)
# print(index)

data = [[] for _ in range(d)]

for i in range(1, d+1):
    num = i
    x, y = index[num-1]
    data[i-1].append(0)
    num += d
    while(num <= h*w):
        x_new, y_new = index[num-1]
        # data[i-1].append(abs(x-x_new)+abs(y-y_new))
        data[i-1].append(abs(x-x_new)+abs(y-y_new)+data[i-1][-1])
        x, y = x_new, y_new
        num += d
# print(data)

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

    index_data = l % d-1

    r = (r-1)//d
    l = (l-1)//d
    print(data[index_data][r]-data[index_data][l])

Submission status: Accepted

Solution code:
h,w,d= map(int,input().split())
loc=[[] for _ in range(w*h+1)]
cost=[0]*(w*h+1)
for i in range(h):
    l= list(map(int,input().split()))
    for j in range(w):loc[l[j]]=[i,j]
for t in range(w*h+1,0,-1):
    if t+d < w*h+1:
        ti,tj=loc[t+d]
        fi,fj=loc[t]
        tempcost= abs(fi-ti)+abs(fj-tj)
        cost[t]=cost[t+d]+tempcost
q= int(input())
for i in range(q):
    l,r= map(int,input().split())
    print(cost[l]-cost[r])