Problem:


Score : 900 points

Problem Statement

There are N squares in a row. The squares are numbered 1, 2, ..., N from left to right.

You have two pieces, initially placed on square A and B, respectively.
You will be asked to process Q queries of the following kind, in the order received:

Given an integer x_i, move one of the two pieces of your choice to square x_i.

Here, it takes you one second to move a piece one square.
That is, the time it takes to move a piece from square X to Y is |X-Y| seconds.

Your objective is to process all the queries in the shortest possible time.

You may only move the pieces in response to queries, and you may not move both pieces at the same time.
Also, it is not allowed to rearrange the order in which queries are given.
It is, however, allowed to have both pieces in the same square at the same time.

Constraints

1 ≤ N, Q ≤ 200,000

1 ≤ A, B ≤ N

1 ≤ x_i ≤ N

Input

Input is given from Standard Input in the following format:

N Q A B
x_1 x_2 ... x_Q

Output

Let the shortest possible time to process all the queries be X seconds. Print X.

Sample Input 1

8 3 1 8
3 5 1

Sample Output 1

7

All the queries can be processed in seven seconds, by:

moving the piece at square 1 to 3

moving the piece at square 8 to 5

moving the piece at square 3 to 1

Sample Input 2

9 2 1 9
5 1

Sample Output 2

4

The piece at square 9 should be moved first.

Sample Input 3

9 2 1 9
5 9

Sample Output 3

4

The piece at square 1 should be moved first.

Sample Input 4

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

Sample Output 4

21



Sample input:
8 3 1 8
3 5 1


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc073/tasks/arc073_d

どちらか片方は前のマスにおいてある
O(N**2)解法は

dp[i][y] = i番目の操作が終わりコマがマスx[i]とyにおいてあるときの最小値
x[0] = A , dp[0][B] = 0 でそれ以外infにしておけばおｋ

dp[i][y] ← dp[i-1][y] + x[i]-x[i-1]
dp[i][x[i-1]] ← min(dp[i-1][y] + |y-x[i]|)

高速化
O(N^2)以下にするには、dpテーブルをいじらないことが必要

dp[i][j] = i番目の位置とj番目のクエリの位置にいるときの最小値
Aを-1,Bを0番目のクエリにしちゃう!

j < i-1の場合 (多くのjではこう)
dp[i][j] = dp[i-1][j] + |x[i]-x[i-1]| →つまり定数足すだけ

j == i-1の場合
dp[i][i-1] = min( dp[i-1][j] + |x[i]-x[j]| )
              j
→x[i]を投げるとこれをすぐ計算する方法が必要…

=======解説を見た========
絶対値をうまく使うのか…(ちょっと思ったが…)

dp[i][y] ← dp[i-1][y] + x[i]-x[i-1]
dp[i][x[i-1]] ← min(dp[i-1][y] + |x[i]-y|)

上側はただ足すだけ (どっかにaddした変数を持っておけばいいだけ)
→具体的には、0基準を-addにする。つまり、新たに代入するときは代入する数字-addにする
→逆にセグ木から取り出したときは、addを足す

下側のクエリは、x[i] >= y に関してはyの寄与負のセグ期から持ってくる (treeL)
                x[i] <  y に関しては逆                              (treeR)

セグ期に入れる数字は treeLでは dp[y]-y treeRではdp[y]+y
"""

#一転更新区間取得のセグ木とRMQである(最大取得したいなら負で突っ込めばおｋ？)
#query区間左,右は実際に求めたい区間(半開区間なので右は+1しておくこと)
#注目ノード番号は0でOK
#担当範囲左,担当範囲右　は、それぞれ　0 , (len(セグ木)+1)//2 にしておくこと

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_upd(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])
    return

def RMQ_upd2(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    if tree[i] < num:
        return
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])
    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return float("inf")
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)


N,Q,A,B = map(int,input().split())
x = list(map(int,input().split()))
x = [A] + x

treeL = make_ST(N+2,float("inf"))
treeR = make_ST(N+2,float("inf"))

add = 0
RMQ_upd(-1*B,B,treeL)
RMQ_upd(B,B,treeR)

for i in range(1,Q+1):

    adp = abs(x[i]-x[i-1])
    
    Lmin = RMQ_query(0,x[i]+1,0,0,(len(treeL)+1)//2,treeL) + add + x[i]
    Rmin = RMQ_query(x[i],N+2,0,0,(len(treeR)+1)//2,treeR) + add - x[i] 

    nmin = min(Lmin,Rmin)
    #print (nmin)
    
    add += adp

    RMQ_upd2(nmin-x[i-1]-add,x[i-1],treeL)
    RMQ_upd2(nmin+x[i-1]-add,x[i-1],treeR)
    

ans = float("inf")
for v in range(N+1):
        j = (len(treeL) - 1) // 2 + v
        tm1 = treeL[j] + add + v
        tm2 = treeR[j] + add - v
        #print (v,tm1,tm2)
        ans = min(ans , tm1 , tm2)
print (ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc073/tasks/arc073_d

どちらか片方は前のマスにおいてある
O(N**2)解法は

dp[i][y] = i番目の操作が終わりコマがマスx[i]とyにおいてあるときの最小値
x[0] = A , dp[0][B] = 0 でそれ以外infにしておけばおｋ

dp[i][y] ← dp[i-1][y] + x[i]-x[i-1]
dp[i][x[i-1]] ← min(dp[i-1][y] + |y-x[i]|)

高速化
O(N^2)以下にするには、dpテーブルをいじらないことが必要

dp[i][j] = i番目の位置とj番目のクエリの位置にいるときの最小値
Aを-1,Bを0番目のクエリにしちゃう!

j < i-1の場合 (多くのjではこう)
dp[i][j] = dp[i-1][j] + |x[i]-x[i-1]| →つまり定数足すだけ

j == i-1の場合
dp[i][i-1] = min( dp[i-1][j] + |x[i]-x[j]| )
              j
→x[i]を投げるとこれをすぐ計算する方法が必要…

=======解説を見た========
絶対値をうまく使うのか…(ちょっと思ったが…)

dp[i][y] ← dp[i-1][y] + x[i]-x[i-1]
dp[i][x[i-1]] ← min(dp[i-1][y] + |x[i]-y|)

上側はただ足すだけ (どっかにaddした変数を持っておけばいいだけ)
→具体的には、0基準を-addにする。つまり、新たに代入するときは代入する数字-addにする
→逆にセグ木から取り出したときは、addを足す

下側のクエリは、x[i] >= y に関してはyの寄与負のセグ期から持ってくる (treeL)
                x[i] <  y に関しては逆                              (treeR)

セグ期に入れる数字は treeLでは dp[y]-y treeRではdp[y]+y
"""

#一転更新区間取得のセグ木とRMQである(最大取得したいなら負で突っ込めばおｋ？)
#query区間左,右は実際に求めたい区間(半開区間なので右は+1しておくこと)
#注目ノード番号は0でOK
#担当範囲左,担当範囲右　は、それぞれ　0 , (len(セグ木)+1)//2 にしておくこと

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_upd(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])
    return

def RMQ_upd2(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = min(tree[i] , num)
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])
    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return float("inf")
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)


N,Q,A,B = map(int,input().split())
x = list(map(int,input().split()))
x = [A] + x

treeL = make_ST(200005,float("inf"))
treeR = make_ST(200005,float("inf"))

add = 0
RMQ_upd(-1*B,B,treeL)
RMQ_upd(B,B,treeR)

for i in range(1,Q+1):

    adp = abs(x[i]-x[i-1])
    
    Lmin = RMQ_query(0,x[i]+1,0,0,(len(treeL)+1)//2,treeL) + add + x[i]
    Rmin = RMQ_query(x[i],200005,0,0,(len(treeR)+1)//2,treeR) + add - x[i] 

    nmin = min(Lmin,Rmin)
    #print (nmin)
    
    add += adp

    RMQ_upd2(nmin-x[i-1]-add,x[i-1],treeL)
    RMQ_upd2(nmin+x[i-1]-add,x[i-1],treeR)
    

ans = float("inf")
for v in range(N+1):
        j = (len(treeL) - 1) // 2 + v
        tm1 = treeL[j] + add + v
        tm2 = treeR[j] + add - v
        #print (v,tm1,tm2)
        ans = min(ans , tm1 , tm2)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return (min(x[0],y[0]),min(x[1],y[1]))
#################

#####ide_ele#####
ide_ele = (10**20,10**20)
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, n,segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num


        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] =self.segfunc(self.tree[k],x)
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import random
def main():
    N,Q,A,B=map(int,input().split())
    x=list(map(int,input().split()))

    Sx=[abs(x[0]-A)]
    Sy=[abs(x[0]-B)]
    for i in range(1,Q):
        Sx.append(abs(x[i]-x[i-1]))
        Sy.append(abs(x[i]-x[i-1]))

    for i in range(1,Q):
        Sx[i]+=Sx[i-1]
        Sy[i]+=Sy[i-1]

    rmqx=SegTree(N+1,segfunc,ide_ele)
    rmqy=SegTree(N+1,segfunc,ide_ele)


    dpx=Sx[0]
    dpy=Sy[0]
    test1=Sx[Q-1]
    test2=Sy[Q-1]
    rmqx.update(A,(-A,A))
    rmqy.update(B,(-B,B))
    for i in range(2,Q+1):
        testx1=rmqx.query(0,x[i-1])[0]+x[i-1]+Sy[i-2]
        testx2=rmqx.query(x[i-1],N+1)[1]-x[i-1]+Sy[i-2]
        dpx=min(testx2,testx1)

        testy1=rmqy.query(0,x[i-1])[0]+x[i-1]+Sx[i-2]
        testy2=rmqy.query(x[i-1],N+1)[1]-x[i-1]+Sx[i-2]
        dpy=min(testy2,testy1)

        rmqx.update(x[i-2],(dpy-Sy[i-1]-x[i-2],dpy-Sy[i-1]+x[i-2]))
        rmqy.update(x[i-2],(dpx-Sx[i-1]-x[i-2],dpx-Sx[i-1]+x[i-2]))
        test1=min(test1,dpx+Sx[Q-1]-Sx[i-1])
        test2=min(test2,dpy+Sy[Q-1]-Sy[i-1])
    

    print(min(test1,test2))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return (min(x[0],y[0]),min(x[1],y[1]))
#################

#####ide_ele#####
ide_ele = (10**20,10**20)
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, n,segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num


        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] =self.segfunc(self.tree[k],x)
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import random
def main():
    N,Q,A,B=map(int,input().split())
    x=list(map(int,input().split()))

    Sx=[abs(x[0]-A)]
    Sy=[abs(x[0]-B)]
    for i in range(1,Q):
        Sx.append(abs(x[i]-x[i-1]))
        Sy.append(abs(x[i]-x[i-1]))

    for i in range(1,Q):
        Sx[i]+=Sx[i-1]
        Sy[i]+=Sy[i-1]

    rmqx=SegTree(N+1,segfunc,ide_ele)
    rmqy=SegTree(N+1,segfunc,ide_ele)


    dpx=Sx[0]
    dpy=Sy[0]
    test1=Sx[Q-1]
    test2=Sy[Q-1]
    rmqx.update(A,(-A,A))
    rmqy.update(B,(-B,B))
    for i in range(2,Q+1):
        testx1=rmqx.query(0,x[i-1])[0]+x[i-1]+Sy[i-2]
        testx2=rmqx.query(x[i-1],N+1)[1]-x[i-1]+Sy[i-2]
        dpx=min(testx2,testx1)

        testy1=rmqy.query(0,x[i-1])[0]+x[i-1]+Sx[i-2]
        testy2=rmqy.query(x[i-1],N+1)[1]-x[i-1]+Sx[i-2]
        dpy=min(testy2,testy1)

        rmqx.update(x[i-2],(dpy-Sy[i-1]-x[i-2],dpy-Sy[i-1]+x[i-2]))
        rmqy.update(x[i-2],(dpx-Sx[i-1]-x[i-2],dpx-Sx[i-1]+x[i-2]))
        test1=min(test1,dpx+Sx[Q-1]-Sx[i-1])
        test2=min(test2,dpy+Sy[Q-1]-Sy[i-1])
    

    print(min(test1,test2))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	#print(res)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

ans_l, ans_r = INF, INF
for i in range(1, n+1):
	ans_l = min(ans_l, dp_l.Access(i) + i)
	ans_r = min(ans_r, dp_r.Access(i) - i)

print(ans_l + total_diff)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

ans_l, ans_r = INF, INF
for i in range(1, n+1):
	ans_l = min(ans_l, dp_l.Access(i) + i)
	ans_r = min(ans_r, dp_r.Access(i) - i)

print(ans_l + total_diff)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**15

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

ans_l, ans_r = INF, INF
for i in range(1, n+1):
	ans_l = min(ans_l, dp_l.Access(i) + i)
	ans_r = min(ans_r, dp_r.Access(i) - i)

print(ans_l + total_diff)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q,A,B,*X = map(int,read().split())

class MinSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) # 葉の要素数
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        INF = 10**18
        self.data = [INF] * (2*self.size)
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x > y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x > y: x = y
            L >>= 1; R >>= 1
        return x

INF = 10**18
dpL = MinSegTree(N+10); dpL.build([INF] * (N+10))
dpR = MinSegTree(N+10); dpR.build([INF] * (N+10))
dpL.update(A,0-A)
dpR.update(A,0+A)

prev_x = B
add = 0
for x in X:
    from_left = dpL.get_value(0,x) + x
    from_right = dpR.get_value(x,N+10) - x
    dist = x-prev_x if x>prev_x else prev_x-x
    y = from_left if from_left < from_right else from_right
    y -= dist
    dpL.update(prev_x,y-prev_x)
    dpR.update(prev_x,y+prev_x)
    add += dist
    prev_x = x

dp = [(x+y)//2 for x,y in zip(dpL.data[dpL.size:],dpR.data[dpR.size:])]
answer = min(dp) + add
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q,A,B,*X = map(int,read().split())

class MinSegTree():
    def __init__(self,N):
        INF = 10**18
        self.Nelem = N
        self.size = 1<<(N.bit_length()) # 葉の要素数
        self.data = [INF] * (2*self.size)
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

def TLE_solution(N,Q,A,B,X):
    INF = 10**18
    dp = [INF] * (N+10)
    dp[A] = 0
    prev_x = B
    add = 0 # dp全体に共通で加算されている値
    for x in X:
        from_left = min(dp[i] + x - i for i in range(x+1))
        from_right = min(dp[i] + i - x for i in range(x+1,N+10))
        dist = x-prev_x if x > prev_x else prev_x-x
        y = min(from_left,from_right)
        dp[prev_x] = y - dist
        add += dist
        prev_x = x
    return min(dp) + add

print(TLE_solution(N,Q,A,B,X))

Submission status: Time Limit Exceeded

Solution code:
LAAAARRRGE = 100000000
N, Q, A, B = map(int, input().split())
xv = list(map(int, input().split()))

dps = []
dps_p = []
dps_m = []
L = N
while True:
    dps.append([LAAAARRRGE for i in range(L)])
    dps_p.append([LAAAARRRGE for i in range(L)])
    dps_m.append([LAAAARRRGE for i in range(L)])
    if L % 2 == 0:
        L = L // 2
    elif L != 1:
        L = L // 2 + 1
    else:
        break

LDEPTH = len(dps)

def update_dps(k, v):
    div = 1
    for d in range(LDEPTH):
        dps[d][k // div] = min(dps[d][k // div], v)
        dps_p[d][k // div] = min(dps_p[d][k // div], v+k)
        dps_m[d][k // div] = min(dps_m[d][k // div], v-k)
        div *= 2

def return_dps(k):
    l = dps[0][k]
    div = 1
    for d in range(LDEPTH):
        if k // div > 0:
            l = min(l, dps_m[d][k // div - 1] + k)
        if k // div < len(dps_m[d]) - 1:
            l = min(l, dps_p[d][k // div + 1] - k)
        div *= 2
    return l
    
# initialize
update_dps(A - 1, 0)

# const to add
xxx = 0
b = B - 1
for j in range(Q):
    xxx += abs(xv[j] - 1 - b)
    # A:a, B:b 
    # move B
    # pass
    # move A
    v = return_dps(xv[j] - 1) - abs(xv[j] - 1 - b)
    # v = min([dps[0][a] + xv[j] - 1 - a for a in range(xv[j] - 1)] + [dps[0][a] - xv[j] + 1 + a for a in range((xv[j] - 1), N)]) - abs(xv[j] - 1 - b)
    # v = min([dps[0][a] + abs(xv[j] - 1 - a) for a in range(N)]) - abs(xv[j] - 1 - b)
    update_dps(b, v)
    # update
    b = xv[j] - 1

print(dps[LDEPTH-1][0] + xxx)

Submission status: Time Limit Exceeded

Solution code:
class MinSegTree:

  def __init__(self, constant, size):

    self.size = size
    self.depth = (size-1).bit_length()
    self.capacity = 1 << self.depth
    self.data = [constant]*(2*self.capacity)

  def _min_interval(self, a, b):
    result = float('inf')
    a += self.capacity
    b += self.capacity
    while a < b:
      if a & 1:
        result = min(result,self.data[a]) 
        a += 1
      if b & 1:
        b -= 1
        result = min(result,self.data[b])
      a >>= 1
      b >>= 1
    return result

  def _set_val(self, a, val):
    a += self.capacity
    while self.data[a] != val and a > 0:
      self.data[a] = val
      val = min(val,self.data[a^1])
      a >>= 1


  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._min_interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.capacity]

  def __setitem__(self, i, x):
    self._set_val(i,x)

  def __iter__(self):
    return iter(self.data[self.capacity:])

N,Q,A,B = map(int,input().split())
t1 = MinSegTree(float('inf'),N)
t2 = MinSegTree(float('inf'),N)

A,B = A-1,B-1
a = A
t1[B] = -B
t2[B] = B
offset = 0

for x in map(int, input().split()):
  x -= 1
  d = abs(x-a)
  offset += d
  m = min(t1[:x] + x - d, t2[x:] - x - d, t1[a]+a)
  t1[a] = m - a
  t2[a] = m + a
  a = x

print(min(map(sum, enumerate(t1))) + offset)