Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.

Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.

Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Accepted

Solution code:
# -*- 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
    
DIC = DD(lambda : [0])

for x in range(D,H*W):
  i = x%D
  DIC[i].append(DIC[i][-1]+abs(posx[x]-posx[x-D])+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(DIC[i][t]-DIC[i][s])

Submission status: Accepted

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(DICY[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: 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)]
dmap={}
for hi in range(h):
  for wi in range(w):
    dmap[a[hi][wi]-1]=(hi+1,wi+1)
dans={}
for di in range(d):
  s=di
  x,y=dmap[di]
  tmp=0
  while s<h*w:
    nx,ny=dmap[s]
    tmp+=abs(x-nx)+abs(y-ny)
    dans[(di,s)]=tmp
    x,y=nx,ny
    s+=d
for l,r in lr:
  l-=1;r-=1
  s=l%d
  print(dans[(s,r)]-dans[(s,l)])
#print(dans)

Submission status: Accepted

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 + 1):
    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: Accepted

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

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

for i in range(h):
    for j in range(w):
        iti[a[i][j]] = (i,j)

for i in range(1,d+1):
    a = 0
    rui[i] = 0
    for j in range(i+d,h*w+1,d):
        a += (abs(iti[j][0] - iti[j-d][0]) + abs(iti[j][1] - iti[j-d][1]))
        rui[j] = a

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[0]+[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  cumsum = list(itertools.accumulate(_))
  X.append(cumsum)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  g=l%D
  if l>r:
    r+=N
    ans=X[g][-1]-X[g][l//D]
    ans+=X[g][r//D]-X[g][0]
  else:
    ans=X[g][r//D]-X[g][l//D]
  
  print(ans)

Submission status: Accepted

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

a={}
for y in range(h):
    tmp=list(map(int,input().split()))

    for x,v in enumerate(tmp):
        a[v]=(y,x)

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

#dis[j]=j%dからjまでのコスト

for i in range(1,h*w+1):
    if i>d:
        bk=a[i-d]
        nx=a[i]
        dis[i]=dis[i-d]+abs(bk[0]-nx[0])+abs(bk[1]-nx[1])

q=int(input())
ans=[]
for _ in range(q):
    start,goal=map(int,input().split())
    ans.append(dis[goal]-dis[start])

for item in ans:
    print(item)

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

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, 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: Accepted

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

Submission status: Accepted

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

cl = [0]*(h*w+1)
for i in range(1,h*w+1):
    if i+d<len(cl):
        f = ad[i]
        t = ad[i+d]
        cl[i+d] = cl[i] + abs(f[0]-t[0]) + abs(f[1]-t[1])

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

Submission status: Accepted

Solution code:
def resolve():
    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)]

    num_to_pos = {}
    for i in range(H):
        for j in range(W):
            num_to_pos[A[i][j]] = (i, j)
    
    acc = [[0] for _ in range(D+1)]
    for i in range(1, D+1):
        num = i
        idx = 0
        while num + D <= H*W:
            _from = num_to_pos[num]
            _to = num_to_pos[num+D]
            acc[i].append(acc[i][idx]+abs(_from[0]-_to[0])+abs(_from[1]-_to[1]))
            num += D
            idx += 1
    
    # print(acc)
    for lr in LR:
        l, r = lr
        series = l%D if l%D != 0 else D
        # print("---")
        # print(series)
        # print(l, r)
        print(acc[series][(r-series)//D] - acc[series][(l-series)//D])
            



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
h , w , d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
zahyo = [-1 for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        zahyo[a[i][j]] = (a[i][j],i,j)
ans = [-1 for i in range(h*w + 1)]
for i in range(1,h*w+1):
    if ans[i] == -1:
        ans[i] = 0
        p = deque()
        p.append(zahyo[i])
        while p:
            now , nowx , nowy = p.popleft()
            if now + d > h*w:
                break
            tugi , nexx , nexy = zahyo[now+d]
            p.append(zahyo[now+d])
            ans[tugi] = ans[now] + abs(nowx-nexx) + abs(nowy-nexy)

    else:
        continue

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

Submission status: Accepted

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

pos = [0] * (h*w + 1)
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (j, i)

dis = [0] * (h*w + 1)
for i in range(h*w+1):
    if i > d:
        x1, y1 = pos[i-d]
        x2, y2 = pos[i]
        dis[i] = abs(x1-x2) + abs(y1-y2) + dis[i-d]

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

    res.append(dis[r]-dis[l])

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_cost(cur, prev):
        return abs(cur[0] - prev[0]) + abs(cur[1] - prev[1])

    h, w, d = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(h)]
    q = int(readline())
    coordinate = dict()

    for row in range(h):
        for col in range(w):
            num = a[row][col]
            coordinate[num] = (row, col)

    cost = dict()

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


class P:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __sub__(self, p):
        return P(self.x-p.x, self.y-p.y)

    def _abs(self):
        return P(abs(self.x), abs(self.y))

    def _sum(self):
        return self.x+self.y

    def to(self, p):
        return (self-p)._abs()._sum()


coodinates = [None]*n
for i in range(h):
    for j, a in enumerate(map(lambda x: int(x)-1, input().split())):
        coodinates[a] = P(i, j)

costs = [[0]for _ in range(d)]
for i in range(d):
    for x, y in zip(paths[i], paths[i][1:]):
        p, q = coodinates[x], coodinates[y]
        costs[i].append(costs[i][-1]+p.to(q))

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  h, w, d = map(int, input().split())
  mat_a = numpy.array([list(map(int, input().split())) for _ in range(h)])
  q = int(input())
  x_to_pos = dict()
  
  for i in range(h):
    for j in range(w):
      x_to_pos[mat_a[i, j]] = (i, j)
      
  def calc_score(p1, p2):
    return sum([abs(x-y) for x, y in zip(p1, p2)])
  
  visited = numpy.zeros((h, w))
  costs = defaultdict(dict)
  for c in range(1, d+1):
    cost = 0
    costs[c%d][c] = 0
    while True:
      cp = x_to_pos[c]
      c += d
      if c > (h*w):
        break
      np = x_to_pos[c]
      cost += calc_score(cp, np)
      costs[c%d][c] = cost
  
  for _ in range(q):
    l, r = map(int, input().split())
    print(abs(costs[l%d][l] - costs[l%d][r]))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
H, W, D = map(int, input().split())
mod_dict = [deque() for _ in range(D)]
h = 0
while h < H:
  A = list(map(int, input().split()))
  w = 0
  while w < W:
    a = A[w]
    mod_dict[a%D].append((a, h, w))
    w += 1
  h += 1
ruiseki_dict = [deque() for _ in range(D)]
d = 0
while d < D:
  m = sorted(mod_dict[d], key=lambda x:x[0])
  py, px = m[0][1], m[0][2]
  ruiseki_dict[d].append(0)
  i = 0 if d == 0 else 1
  while i < len(m):
    ry, rx = m[i][1], m[i][2]
    ruiseki_dict[d].append(ruiseki_dict[d][-1]+abs(ry-py)+abs(rx-px))
    py, px = ry, rx
    i += 1
  d += 1
Q = int(input())
for _ in range(Q):
  l, r = list(map(int, input().split()))
  d = ruiseki_dict[r%D]
  print(d[r//D]-d[l//D])

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

h,w,d=map(int,input().split())
dic={i:0 for i in range(1,h*w+1)}
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        dic[l[j]]=(i+1,j+1)
q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
res=[[] for _ in range(d)]
for i in range(1,h*w-d+1):
    x,y=dic[i]
    s,t=dic[i+d]
    power=abs(x-s)+abs(y-t)
    res[i%d].append(power)
for i in range(d):
    length=len(res[i])
    x=0
    for j in range(length):
        x+=res[i][j]
        res[i][j]=x
for i in range(q):
    l,r=lr[i]
    if l==r:
        print(0)
        continue
    else:
        mod=l%d
        quol=l//d
        quor=r//d-1
        if mod==0:
          quol-=1
          quor-=1
        if quol==0:
          print(res[mod][quor])
        else:
          quol-=1
          print(res[mod][quor]-res[mod][quol])

Submission status: Accepted

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

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

route = [0] * (H * W + 1)
for i in range(H):
  line = list(map(int,readline().split()))
  for j in range(len(line)):
    route[line[j]] = (i,j)

# 1,2,3 ... の頂点番号を格納した配列を作る
# D個おきに距離を格納する

dist = [0] * (H * W + 1)
for i in range(D + 1,len(route)):
  gy,gx = route[i]
  sy,sx = route[i - D]
  dist[i] = abs(gy - sy) + abs(gx - sx) 
  dist[i] = dist[i] + dist[i - D]


Q = int(readline())

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

Submission status: Accepted

Solution code:
h, w, d = [int(x) for x in input().split()]
n = h * w

p_list = [None] * (n + 1)
for i in range(h):
    a_list = [int(x) for x in input().split()]
    for j in range(w):
        p_list[a_list[j]] = (i, j)

m_a_list = [0] * (n + 1)
for start in range(1, d + 1):
    p_i, p_j = p_list[start]
    p_target = start
    for target in range(start + d, n + 1, d):
        n_i, n_j = p_list[target]
        m = abs(n_i - p_i) + abs(n_j - p_j)
        m_a_list[target] = m + m_a_list[p_target]
        p_i, p_j, p_target = n_i, n_j, target

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

Submission status: Accepted

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

mat_map = [()]*(h*w+1)

for i in range(h):
    for j in range(w):
        mat_map[a[i][j]] = (i, j)

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

for i in range(h*w-1, 0, -1):
    if i+d > h*w:
        continue
    current = mat_map[i]
    nex = mat_map[i+d]
    dist = abs(current[0]-nex[0]) + abs(current[1]-nex[1])
    dp[i] = dp[i+d] + dist

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

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

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline

def myindex(l, element, default=-1):
    if element in set(l):
        return l.index(element)
    else:
        return default

def main():
    H, W, D = map(int, input().split())
    grid = []; locale = [0]*(H*W)
    for i in range(H):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            x, y = i+1, j+1
            locale[t-1] = (x, y)
        grid.append(tmp)
    
    power = []
    for k in range(H*W-D):
        fr = locale[k]
        to = locale[k+D]
        need = abs(fr[0]- to[0]) + abs(fr[1] - to[1])
        power.append(need)
    
    cum = []
    for d in range(D):
        cum.append([0] + list(itertools.accumulate(power[d::D])))

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        d = (L-1)%D
        dnum = (L-1)//D
        drange = (R-L)//D
        ans = cum[d][dnum+drange] - cum[d][dnum]
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
# 座標記録
cords = [0] * (h*w+1)
for i in range(h):
    line = tuple(map(int, input().split()))
    for j in range(w):
        cords[line[j]] = (i, j)

# グループごとの累積和
acccosts = [0] * (h*w+1)
for num in range(1, h*w+1-d):
    nxy = cords[num]
    nnxy = cords[num+d]
    acccosts[num+d] = acccosts[num] + abs(nxy[0]-nnxy[0]) + abs(nxy[1] - nnxy[1])

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

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
dp=[0]*(h*w)
for i in range(d+1,h*w+1):
    x,y=ind[i]
    z,q=ind[i-d]
    dp[i-1]=abs(z-x)+abs(y-q)+dp[i-d-1]


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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


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

"""
# 飛ばし累積和
N = 10
num = [i for i in range(1, N + 1)]
D = 2
lista = [0] * N
for i in range(D):
    for j in range(i, N, D):
        if j == i:
            lista[j] = num[j]
        else:
            lista[j] = num[j] + lista[j - D]
# [1, 2, 4, 6, 9, 12, 16, 20, 25, 30]
print(lista)
# 9番目までの奇数の数字の合計 - 1番目までの奇数の数字の合計
# 3 + 5 + 7 + 9
print(lista[8] - lista[0])
"""

# Dかそれぞれのqueryで固定なのでこの問題は解ける
H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()
# piece[0]からpiece[1]まで
# 4 → 6　→ 8
piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]

# 飛ばし累積和
x_plus = [0] * (H * W)
y_plus = [0] * (H * W)
for i in range(D):
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
            x_plus[j] = opt_x + x_plus[j - D]
            y_plus[j] = opt_y + y_plus[j - D]

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    x_point = x_plus[goal - 1] - x_plus[start - 1]
    y_point = y_plus[goal - 1] - y_plus[start - 1]
    return x_point + y_point

for i in range(Q):
    print(past_exam(piece[i]))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


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

# Dかそれぞれのqueryで固定なのでこの問題は解ける
H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()
# piece[0]からpiece[1]まで
# 4 → 6　→ 8
piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]

# 飛ばし累積和
x_plus = []
y_plus = []
for i in range(D):
    list_x = [0]
    list_y = [0]
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
        list_x.append(list_x[-1] + opt_x)
        list_y.append(list_y[-1] + opt_y)
    list_x.pop(0)
    list_y.pop(0)
    x_plus.append(list_x)
    y_plus.append(list_y)

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    mul = (start - 1) % D
    if D == 1:
        x_point = x_plus[0][goal - 1] - x_plus[0][start - 1]
        # 書き間違い!!
        y_point = y_plus[0][goal - 1] - y_plus[0][start - 1]
    else:
        x_point = x_plus[mul][(goal - mul) // D] - x_plus[mul][(start - mul) // D]
        y_point = y_plus[mul][(goal - mul) // D] - y_plus[mul][(start - mul) // D]
    return x_point + y_point

for i in range(Q):
    print(past_exam(piece[i]))

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(h):
    for j in range(w):
        dic[a[i][j]] = i,j

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

for i in range(d+1,h*w+1):
    if i-d not in dic:
        continue
    li[i] = li[i-d] + abs(dic[i][0]-dic[i-d][0]) + abs(dic[i][1]-dic[i-d][1])

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