Problem:


Score : 400 points

Problem Statement

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

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

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

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

The i-th test will be conducted as follows:

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

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

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

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

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

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

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

1 \leq Q \leq 10^5

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

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

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

Output

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

Output should be in the order the tests are conducted.

Sample Input 1

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

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

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

Sample Input 2

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

Sample Output 2

0
0

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

Sample Input 3

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

Sample Output 3

0
5
0



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


Sample output:
5

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        index[A[i][j]]=[i,j]
        
    
S=[[0]*(H*W//D+1) for _ in range(D+1)]
for start in range(1,D+1):
    for j in range(H*W//D):
        prev=start+j*D
        nxt=prev+D
        if nxt>H*W:
            break
        diff=abs(index[nxt][0] - index[prev][0]) + abs(index[nxt][1] - index[prev][1])
        S[start][j+1]=S[start][j]+diff
        
Q=int(input())
        
for i in range(Q):
    L,R=map(int,input().split())
    start=L%D
    if start==0:
        start=D
    print(S[start][(R-start)//D] - S[start][(L-start)//D])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

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

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [None] * (H * W + 1)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B[H * W] = (0, (-1, -1))
B = sorted(B, key=lambda x: x[0])
costs = [0] * (H * W + 1)
for i in range(H * W, 0, -1):
    if i + D <= H * W:
        costs[i] = costs[i + D] + abs(B[i][1][0] - B[i + D][1][0]) + abs(B[i][1][1] - B[i + D][1][1])

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
mass = np.array([(0, 0) for _ in range(num + 1)])
mp = np.zeros(num+1)
for i in range(1, h+1):
    for j, a in enumerate(map(int, input().split())):
        mass[a] = [i, j+1]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(int(mp[r]-mp[l]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
x = [0] * (num + 1)
y = [0] * (num + 1)
mp = [0] * (num + 1)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        x[a], y[a] = [i+1, j+1]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + abs(x[i] - x[i-d]) + abs(y[i] - y[i-d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
dic=[0]*(h*w+1)
def cost(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        dic[a[j]]=(i+1,j+1)
dis=[[0] for i in range(d)]
for i in range(d):
    k=1
    for j in range(i+d,h*w,d):
        dis[i].append(dis[i][k-1]+cost(dic[j-d+1],dic[j+1]))
        k+=1
# print(dis)
q=int(input())
ans=0
for i in range(q):
    l,r=map(int,input().split())
    k=l%d-1
    print(dis[k][(r+d-1)//d-1]-dis[k][(l+d-1)//d-1])

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


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)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(h)]

    dd = defaultdict(list)
    for i in range(h):
        for j in range(w):
            dd[a[i][j]] = [i,j]

    d2 = defaultdict(int)
    for i in range(d):
        n = 1 + i
        v = 0
        x,y = dd[n]
        while n <= h * w - d:
            n += d
            xx,yy = dd[n]
            v += abs(xx - x) + abs(yy - y)
            x = xx
            y = yy
            d2[n] = v
            
    q = int(input())
    for i in range(q):
        l, r = map(int, input().split())
        print(d2[r] - d2[l])
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
h,w,d = map(int,input().split())
ans = 0
x = [0]*(h*w+1)
y = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        x[a[j]] = j
        y[a[j]] = i
q = int(input())
#飛び飛びの累積和をとる　視点と
cum_sum_d = [0]*(h*w+1)
for i in range(d,h*w+1):
    cum_sum_d[i] =  cum_sum_d[i-d] + abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for i in range(q):
    l,r = map(int,input().split())
    ans = cum_sum_d[r] - cum_sum_d[l]
    
    """ #TLE解
    for i in range((r-l)//d): 
        ans += abs(x[l+d*i]-x[l+d*(i+1)])+abs(y[l+d*i]-y[l+d*(i+1)])
        """
    print(ans)

Submission status: Accepted

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

def main():
    H,W,D = map(int,input().split())
    A = [None] * (H*W+1)
    for i in range(H):
        j = 1
        for x in input().split():
            # [消費魔力の総和, 座標]
            A[int(x)] = [0,(i+1,j)]
            j += 1

    # 累積和を求める O(H*W)
    for i in range(1,H*W+1):
        if i <= D:
            continue
        A[i][0] += A[i-D][0]
        A[i][0] += abs(A[i][1][0] - A[i-D][1][0])
        A[i][0] += abs(A[i][1][1] - A[i-D][1][1])

    # クエリ O(1)
    Q = int(input())
    for _ in range(Q):
        L, R = map(int,input().split())

        print(A[R][0] - A[L][0])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
    H,W,D = map(int,input().split())
    A = [None] * (H*W+1)
    for i in range(H):
        j = 1
        for x in input().split():
            A[int(x)] = [0,(i+1,j)]
            j += 1

    for i in range(1,H*W+1):
        if i <= D:
            continue
        A[i][0] += A[i-D][0]
        A[i][0] += abs(A[i][1][0] - A[i-D][1][0])
        A[i][0] += abs(A[i][1][1] - A[i-D][1][1])

    # クエリ
    Q = int(input())
    for _ in range(Q):
        L, R = map(int,input().split())

        print(A[R][0] - A[L][0])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
h = 0--(H*W+1)//D

pos = [[INF]*h for _ in range(D)]
for i,row in enumerate(A):
    for j,a in enumerate(row):
        d,m = divmod(a,D)
        pos[m][d] = (i,j)

dists = [[0] for _ in range(D)]
for i,p in enumerate(pos):
    for p1,p2 in zip(p,p[1:]):
        if p1==INF or p2==INF: continue
        a1,b1 = p1
        a2,b2 = p2
        dist = abs(a1-a2) + abs(b1-b2)
        dists[i].append(dists[i][-1] + dist)

ans = []
for l,r in LR:
    a,i = divmod(l,D)
    b,j = divmod(r,D)
    if i==0:
        a-=1; b-=1
    ans.append(dists[i][b] - dists[i][a])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
dic={}
h,w,d=map(int,input().split())
def cost(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        dic[a[j]]=(i+1,j+1)
dis=[[0] for i in range(d)]
for i in range(d):
    k=1
    for j in range(i+d,h*w,d):
        dis[i].append(dis[i][k-1]+cost(dic[j-d+1],dic[j+1]))
        k+=1
# print(dis)
q=int(input())
ans=0
for i in range(q):
    l,r=map(int,input().split())
    k=l%d-1
    print(dis[k][(r+d-1)//d-1]-dis[k][(l+d-1)//d-1])

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


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)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(h)]

    dd = defaultdict(list)
    for i in range(h):
        for j in range(w):
            dd[a[i][j]] = [i,j]

    d2 = defaultdict(int)
    for i in range(d):
        n = 1 + i
        v = 0
        x,y = dd[n]
        while n <= h * w - d:
            n += d
            xx,yy = dd[n]
            v += abs(xx - x) + abs(yy - y)
            x = xx
            y = yy
            d2[n] = v
    q = int(input())
    for i in range(q):
        l, r = map(int, input().split())
        if l == r:
            print(0)
        elif l == 0:
            print(d2[r])
        else:
            print(d2[r] - d2[l])
        



            


    




    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    H,W,D=MI()
    A=LLIN(H)
    Q=I()
    LR=LLIN(Q)

    xy = [0]*(H*W+1)
    for i in range(H):
        for j in range(W):
            xy[A[i][j]]=(i,j)
    
    def calc_cost(A,B):
        x,y = xy[A]
        w,z = xy[B]
        return abs(x-w)+abs(y-z)

    cost = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i-D>0:
            cost[i] = cost[i-D] + calc_cost(i,i-D)
    for l,r in LR:
        print(cost[r]-cost[l])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

H, W, D = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(H)]
Q = int(readline())
query = [tuple(map(int, readline().split())) for _ in range(Q)]

path = [[(-1, -1)]*((H*W)//D+1) for _ in range(D)]
for i in range(H):
    for j in range(W):
        a = A[i][j]
        div, mod = divmod(a, D)
        path[mod][div] = (i, j)
path[0][0] = path[0][1]

cost = []
for i in range(D):
    tmp = [0]
    for l, r in zip(path[i][:-1], path[i][1:]):
        x, y = l
        z, w = r
        tmp.append(tmp[-1] + abs(z - x) + abs(w - y))
    cost.append(tmp)

ans = []
for L, R in query:
    vl, md = divmod(L, D)
    vr = R // D

    tmp = cost[md][vr] - cost[md][vl]
    ans.append(tmp)

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

Submission status: Accepted

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 diff(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def main():
    H, W, D = LI()
    A = []
    for _ in range(H):
        A.append(LI())
    Q = I()
    LR = []
    for _ in range(Q):
        LR.append(LI())
    nums = [[] for _ in range(90000)]
    valAndPoint = []
    for r in range(H):
        for c in range(W):
            valAndPoint.append((A[r][c], (r, c)))
    valAndPoint = sorted(valAndPoint, key=lambda x: x[0])
    dists = [[] for _ in range(90000)]
    for val, point in valAndPoint:
        nums[val % D].append(point) # val // D番目
    cum_nums = [[0] for _ in range(90000)]
    for amari, points in enumerate(nums):
        if len(points) < 1:
            continue
        cur_p = points[0]
        for p in points[1:]:
            dists[amari].append(diff(cur_p, p))
            ix = len(dists[amari])
            cum_nums[amari].append(cum_nums[amari][ix-1] + diff(cur_p, p))
            cur_p = p
    for lr in LR:
        l = lr[0]
        r = lr[1]
        l_amari = l % D

        st_hops = l // D
        en_hops = r // D
        if l % D == 0:
            st_hops -= 1
            en_hops -= 1
        print(cum_nums[l_amari][en_hops] - cum_nums[l_amari][st_hops])
main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#途中

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

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

loc=[[0,0] for i in range(W*H)]

#print(loc)

for i in range(H):
    for j in range(W):
        loc[A[i][j]-1][0]=i
        loc[A[i][j]-1][1]=j
        #print(loc)
#print(loc)

cost=[[0]*((H*W)//D) for i in range(D)]

for i in range((H*W)%D):
    cost[i].append(0)

for i in range(D):
    pass
    count=1
    temp=i
    while temp+D<(H*W):
        temp=i+D*count
        cost[temp%D][temp//D]=abs(loc[temp][0]-loc[temp-D][0])+abs(loc[temp][1]-loc[temp-D][1])+cost[temp%D][temp//D-1]
        count+=1
        #print(cost)
cost[-1]=[0]+cost[-1]

Q=int(input())
for _ in range(Q):
    x,y=map(int,input().split())
    #print(cost[x%D-1][x//D-1])
    print(cost[y%D-1][y//D]-cost[x%D-1][x//D])

#print(cost)

Submission status: Accepted

Solution code:
h,w,D = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
px = [0]*(h*w+1)
py = [0]*(h*w+1)
d = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        px[a[i][j]] = i
        py[a[i][j]] = j

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:
from bisect import *
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
zahyou=[[0,0] for i in range(H*W+1)]
for h in range(H):
    for w in range(W):
        zahyou[A[h][w]][0]=h
        zahyou[A[h][w]][1]=w
dp=[0 for i in range(H*W+1)]
for i in range(len(dp)):
    if i>=D:
        A1=zahyou[i][0]-zahyou[i-D][0]
        A2=zahyou[i][1]-zahyou[i-D][1]
        if A1<0:A1=-A1
        if A2<0:A2=-A2
        dp[i]=dp[i-D]+A1+A2

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

Submission status: Accepted

Solution code:
from bisect import *
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
zahyou=[[0,0] for i in range(H*W+1)]
for h in range(H):
    for w in range(W):
        zahyou[A[h][w]][0]=h
        zahyou[A[h][w]][1]=w
dp=[0 for i in range(H*W+1)]
for i in range(len(dp)):
    if i>=D:
        dp[i]=dp[i-D]+int(abs(zahyou[i][0]-zahyou[i-D][0]))+int(abs(zahyou[i][1]-zahyou[i-D][1]))

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

Submission status: Accepted

Solution code:

#import numpy as np


def acinput():
    return list(map(int, input().split(" ")))


mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


H, W, D = acinput()
# Ad={}
Ad = [0]*(H*W+1)
for i in range(H):
    ar = acinput()
    for j, sar in enumerate(ar):
        # Ad[sar]=np.array((i,j))
        Ad[sar] = (i, j)

#dp = [[0 for j in range(H*W+1)]for i in range(H*W+1)]
d = [0]*(H*W+1)

# for x in range(1, H*W+1):
#    dp[x][x]=0

y = D+1
while True:
        if y > H*W:
            break
        # print(x,y)
        #tmp = Ad[y]-Ad[y-D]
        #S = np.sum(np.abs(tmp[0])+abs(tmp[1]))
        #tmp = Ad[y]-Ad[y-D]
        S = abs(Ad[y][0]-Ad[y-D][0])+abs(Ad[y][1]-Ad[y-D][1])

        # dp[x][y]=dp[x][y-D]+S
        d[y] = d[y-D]+S
        y += 1


# print(np.array(dp))

Q = int(input())
for i in range(Q):
    l, r = acinput()
    print(d[r]-d[l])


# print(Ad)
# print(np.array(dp))
#print(d)

Submission status: Accepted

Solution code:
# coding: utf-8
H,W,D=map(int,input().split())
num=[[] for i in range(H*W+1)]

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

cost=[0 for i in range(D)]

for i in range(H*W-D):
    cost.append(cost[i] + abs(num[H*W-i][0]-num[H*W-i-D][0]) + abs(num[H*W-i][1]-num[H*W-i-D][1]))

cost.append(None)

cost.reverse()

Q=int(input())

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

Submission status: Accepted

Solution code:
# ABC089 D - Practical Skill Test
h,w,d=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
x=[0]*(h*w+1)
y=[0]*(h*w+1)
ans=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        x[a[i][j]]=i
        y[a[i][j]]=j
for i in range(d+1,h*w+1):
    ans[i]=ans[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
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())
px = [0] * (H*W+1)
py = [0] * (H*W+1)
d = [0] * (H*W+1)

for y in range(H):
    line = list(map(int, input().split()))
    for x, A in enumerate(line):
        px[A] = x
        py[A] = y

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:
import sys
readline = sys.stdin.buffer.readline

H, W, D = map(int, readline().split())
px = [0] * (H*W+1)
py = [0] * (H*W+1)
d = [0] * (H*W+1)

for y in range(H):
    line = list(map(int, readline().split()))
    for x, A in enumerate(line):
        px[A] = x
        py[A] = y

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)]
px=[0]*(h*w)
py=[0]*(h*w)
for i in range(h):
  for j in range(w):
    px[a[i][j]-1]=j
    py[a[i][j]-1]=i
dis=[0]*(h*w+1)
for i in range(d,h*w):
  dis[i]=dis[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(dis[r-1]-dis[l-1])

Submission status: Accepted

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

# queryがたくさんある系
# query一つにつきO(1)ぐらいで応答しないと行けない→前処理の必要あり

# あるマスについてはD倍したマスだけ把握しておけばいいんじゃない？
'''
D=2
1 4 3
2 5 7
8 9 6
'''
# だったらstart=1,2において、移動のスコアの累積和を入れていく
# Qに回答時は、L%D番目のstartの累積和において、L//Dにおいて累積和の差を求めれば良い
# ピッタリDだった場合に面倒なので-0.5して置くのは良いかもしれない

from collections import defaultdict
from itertools import accumulate
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def get_cost(i, j, x, y):
    return abs(x - i) + abs(y - j)


H, W, D = read_ints()
A = read_matrix(H)
ruiseki = defaultdict(lambda: [])
num_to_co = {}

for i, a in enumerate(A):
    for j, aa in enumerate(a):
        num_to_co[aa] = (i, j)

for num in range(1, D + 1):
    pre_i, pre_j = num_to_co[num]
    pre_num = num
    ruiseki[num].append(0)
    while W * H >= pre_num + D:
        now_num = pre_num + D
        i, j = num_to_co[now_num]
        cost = get_cost(pre_i, pre_j, i, j)
        ruiseki[num].append(cost)
        # 必要なもの、前のi,j今のi,j 今の番号
        # 更新するもの 前のi,j←今のi,j 今の番号を次の番号に
        pre_i, pre_j = i, j
        pre_num = now_num

    ruiseki[num] = list(accumulate(ruiseki[num]))
# print(ruiseki)

# Qに答える番だ
Q = int(input())
for _ in range(Q):
    L, R = read_ints()
    tmp = ruiseki[L % D if L % D != 0 else D]
    # print(tmp)
    # print((R - 1) // D, (L - 1) // D)
    print(tmp[(R - 1) // D] - tmp[(L - 1) // D])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
p=[0]*(h*w)
for i in range(h):
  a=list(map(int,input().split()))
  for j in range(w):p[a[j]-1]=(i,j)
x=[0]*d
calc=lambda x1,y1,x2,y2:abs(x1-x2)+abs(y1-y2)
for i in range(d,h*w):
  x.append(x[i-d]+calc(p[i][0],p[i][1],p[i-d][0],p[i-d][1]))
for i in range(int(input())):
  l,r=map(int,input().split())
  print(x[r-1]-x[l-1])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
px = [0]*(h*w+1)
py = [0]*(h*w+1)
for i in range(h):
    l = list(map(int,input().split()))
    for j in range(w):
        px[l[j]],py[l[j]] = i,j  

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

n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    print(count[b]-count[a])

Submission status: Accepted

Solution code:
h,w,d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
q=int(input())
b=[list(map(int, input().split())) for i in range(q)]
import collections
from collections import defaultdict
x=defaultdict(int)



for i in range(h):
    for j in range(w):
        x[i,j]=a[i][j]
x1=sorted(x.items(),key=lambda x:x[1])

ans=[[0]*(-(h*w//-d)) for i in range(d)]


for i in range(d):
    count=0
    for j in range(1,-(h*w//-d)):
        if i+j*d>=h*w:
            continue
        count+=abs(x1[i+(j-1)*d][0][0]-x1[i+j*d][0][0])
        count+=abs(x1[i+(j-1)*d][0][1]-x1[i+j*d][0][1])
        ans[i][j]+=count

for i in range(q):
    u=(b[i][0]-1)%d
    u1=(b[i][0]-1-u)//d
    v=(b[i][1]-b[i][0])//d

    print(ans[u][u1+v]-ans[u][u1])

Submission status: Accepted

Solution code:
def solve(h, w, d, AA, q, LR):
    Ainv = {
        AA[y][x]: (x, y)
        for x in range(w)
        for y in range(h)
    }
    costs = [0] * (h * w)
    for i in range(d , h * w):
        xf, yf = Ainv[i - d + 1]
        xt, yt = Ainv[i + 1]
        costs[i] = costs[i - d] + abs(xt - xf) + abs(yt - yf)

    ret = [0] * q
    for i, (l, r) in enumerate(LR):
        ret[i] = costs[r - 1] - costs[l - 1]

    return ret

_h, _w, _d = map(int, input().split())
_AA = [list(map(int, input().split())) for _ in range(_h)]
_q = int(input())
_LR = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_h, _w, _d, _AA, _q, _LR), sep='\n')

Submission status: Accepted

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

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

d = []
for i in range(H*W+1):
    if i <= D:
        d.append(0)
    else:
        d.append(d[i-D] + abs(p[i][0] - p[i-D][0]) + abs(p[i][1] - p[i-D][1]))

for i in range(Q):
    print(d[LR[i][1]] - d[LR[i][0]])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    H, W, D = Scanner.map_int()
    A = Scanner.int_list_list(H)
    Q = Scanner.int()
    query = Scanner.int_list_list(Q)
    M = [0] * (H*W + 1)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = (w, h)
    S = [0] * (H * W + 1)
    for i in reversed(range(1, H*W+1)):
        if i + D >= H*W+1:
            S[i] = 0
        else:
            S[i] = S[i+D] + abs(M[i][0] - M[i+D][0]) + abs(M[i][1] - M[i+D][1])
    for q in query:
        print(S[q[0]] - S[q[1]])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
h, w, d = list(map(int, input().split()))
grid = []
num = [[] for i in range(h*w+1)]
for i in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    for j in range(w):
        num[grid[i][j]]=[j+1, i+1]
k = math.ceil((h*w+1) / d)
#initialize
cost = [[0 for i in range(k)] for j in range(d)]
for i in range(d + 1,h*w+1):
    x, y = num[i]
    prex, prey = num[i - d]
    cost[i % d][i//d] = abs(prex - x) + abs(prey - y)
    cost[i % d][i//d] += cost[i % d][(i - d)// d]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r%d][r//d] - cost[l%d][l//d])