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:
class MinSegTree:

  def __init__(self, initial_data):

    initial_data = list(initial_data)
    self.original_size = len(initial_data)
    self.depth = (len(initial_data)-1).bit_length()
    self.size = 1 << self.depth
    self.data = [0]*self.size + initial_data + [0]*(self.size - len(initial_data))
    self.offset = 0

    for d in reversed(range(self.depth)):
      a = 1 << d
      b = a << 1
      for i in range(a,b):
        self.data[i] = min(self.data[2*i],self.data[2*i+1])

  def _min_interval(self, a, b):
    
    def rec(i, na, nb):
      if b <= na or nb <= a:
        return float('inf')
      if a <= na and nb <= b:
        return self.data[i]
      split = (na+nb)//2
      return min(rec(2*i, na, split), rec(2*i+1, split, nb))

    return rec(1, 0, self.size)

  def _set_val(self, a, val):
    def rec(i, na, nb):
      if na == a == nb-1:
        self.data[i] = val
      elif na <= a < nb:
        split = (na+nb)//2
        self.data[i] = min(rec(2*i, na, split), rec(2*i+1, split, nb))
      return self.data[i]
    rec(1, 0, self.size)

  def add_to_all(self, val):
    self.offset += val

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

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

  def __iter__(self):
    def gen():
      for x in self.data[self.size:]:
        yield x
    return gen


"""
dp[i][b] = dp[i-1][b] + |x-a| for all b
dp[i][a] = min(dp[i-1][b] + |x-b| for all b)
         = min(dp[i-1][j] - j + x for j = [0,x]), min(dp[i-1][j]+j-x for j = (x,n])

dp[i][j] - j と dp[i][j] + jをセグ木でもつ
"""

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

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

print(min(t1[i]+t2[i] for i in range(N))//2)

Submission status: Time Limit Exceeded

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


# aを動かす場合、cost[b] <- cost[b] + |x-a|
# bを動かす場合、cost[a] <- cost[b] + |x-b|

a = A
dp = {B:0}

for x in map(int,input().split()):
  ndp = {}
  xa = abs(x-a)
  for b,c in dp.items():
    ndp[b] = c + xa

  ndp[a] = min(c+abs(x-b) for b,c in dp.items())

  dp = ndp
  a = x

print(min(dp.values()))

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(N)] for j in range(Q+1)]
for a in range(N):
    dp[0][a] = LAAAARRRGE
dp[0][A - 1] = 0


b = B - 1
for j in range(Q):
    # A:a, B:b 
    # move B
    for a in range(N):
        dp[j+1][a] = dp[j][a] + abs(xv[j] - 1 - b)
    # move A
    dp[j+1][b] = min(dp[j+1][b], min([dp[j][a] + abs(xv[j] - 1 - a) for a in range(N)]))
    # update
    b = xv[j] - 1

print(min([dp[Q][a] for a in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np
import math

class SegmentTree():
    INFINITY = 1000000001
    N = 0
    Data = np.ones(0)
    def __init__(self, _N):
        self.N = 2**math.ceil(math.log(_N, 2) + 1) -1
        self.Data = np.ones(self.N)*self.INFINITY

    def update(self, i, x):
        index = i + self.N/2
        self.Data[index] = x
        while index > 0:
            index= int((index-1)/2)
            self.Data[index] = min(self.Data[2*index + 1],self.Data[2*index+2])
    
    def query(self, a, b, k = 0, l = 0, r = None):
        if r is None:
            r = int(self.N+1)/2
        if (r <=a or b <= l):
            return self.INFINITY
        if (a <= l and r <= b):
            return self.Data[k]
        else:
            vl = self.query(a,b,k*2+1,l,int((l+r)/2))
            vr = self.query(a,b,k*2+2,int((l+r)/2),r)
            return min([vl,vr])
    
    def add(self,x):
        self.Data += x 

    def get(self,i):
        return self.Data[i + int(self.N/2)]
    
    def getData(self):
        return self.Data[int(self.N/2):]

N, Q, A, B =map(int, input().split())
X = list(map(int, input().split()))

DP_minusj = SegmentTree(N+1)
DP_plusj = SegmentTree(N+1)

DP_minusj.update(A,0 - A)
DP_plusj.update(A,0 + A)

beforeX = B

for i in range(Q):
    min_minus = DP_minusj.query(1, X[i]+1) + X[i]
    min_plus = DP_plusj.query(X[i]+1, N+1) - X[i]
    DP_minusj.add(abs(X[i] - beforeX))
    DP_plusj.add(abs(X[i] - beforeX))
    newDP_Xij =  min(min_minus, min_plus)
    DP_minusj.update(beforeX,newDP_Xij - beforeX)
    DP_plusj.update(beforeX,newDP_Xij + beforeX)
    beforeX = X[i] 
print(int(min(DP_minusj.getData()[:N+1] + np.arange(N+1))))

Submission status: Time Limit Exceeded

Solution code:
n, x, a, b = [int(_) for _ in raw_input().split()]
x = [int(_) for _ in raw_input().split()]

p = {(a, b): 0}


def r(k, v):
    if k in np and v >= np[k]:
        return
    np[k] = v


for xi in x:
    np = {}
    for (oa, ob), ov in p.iteritems():
        r((oa, xi), ov + abs(ob - xi))
        r((xi, ob), ov + abs(oa - xi))
    p = np

print(min(p.itervalues()))

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import collections
import functools

class memoized(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if not isinstance(args, collections.Hashable):
            return self.func(*args)

        elif args in self.cache:
            return self.cache[args]

        else:
            value = self.func(*args)
            self.cache[args] = value
            return value

    def __repr__(self):
        return self.func.__doc__

    def __get__(self, obj, objtype):
        return functools.partial(self.__call__, obj)


@memoized
def besttime(querys, a, b):
    if len(querys) == 0:
        return 0
    querys = list(querys)
    q = querys.pop(0)
    return min(besttime(tuple(querys), a, q) + abs(b-q), besttime(tuple(querys), q, b) + abs(a-q))


N, Q, A, B = [int(i) for i in raw_input().split()]
querys = [int(i) for i in raw_input().split()]
print besttime(tuple(querys), A, B)

Submission status: Accepted

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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, W = na()
INF = 10 ** 12
dp = [[-INF] * (N*3+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = na()
    if i == 0:
        w1 = w
    w -= w1
    for j in range(N, 0, -1):
        for k in range(N*3, -1, -1):
            if k >= w:
                dp[j][k] = max(dp[j][k], dp[j-1][k-w] + v)

ans = 0
for i in range(1, N+1):
    wmax = W - w1 * i
    if wmax < 0:
        break
    ans = max(ans, max(dp[i][0:min(N, wmax) + 1]))

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import collections
import functools
from random import randint
from sys import setrecursionlimit

class memoized(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if not isinstance(args, collections.Hashable):
            return self.func(*args)

        elif args in self.cache:
            return self.cache[args]

        else:
            value = self.func(*args)
            self.cache[args] = value
            return value

    def __repr__(self):
        return self.func.__doc__

    def __get__(self, obj, objtype):
        return functools.partial(self.__call__, obj)


def answer(querys, A, B):
    N = len(querys)
    @memoized
    def besttime(n, a, b):
        if n == 0:
            return 0
        q = querys[N-n]
        return min(besttime(n-1, a, q) + abs(b-q), besttime(n-1, q, b) + abs(a-q))

    return besttime(len(querys), A, B)

setrecursionlimit(200000)
N, Q, A, B = [int(i) for i in raw_input().split()]
querys = [int(i) for i in raw_input().split()]
print answer(querys, A, B)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import collections
import functools

class memoized(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if not isinstance(args, collections.Hashable):
            return self.func(*args)

        elif args in self.cache:
            return self.cache[args]

        else:
            value = self.func(*args)
            self.cache[args] = value
            return value

    def __repr__(self):
        return self.func.__doc__

    def __get__(self, obj, objtype):
        return functools.partial(self.__call__, obj)


def answer(querys, a, b):
    N = len(querys)
    @memoized
    def besttime(n, a, b):
        if n == 0:
            return 0
        q = querys[N-n]
        return min(besttime(n-1, a, q) + abs(b-q), besttime(n-1, q, b) + abs(a-q))

    return besttime(len(querys), a, b)


N, Q, A, B = [int(i) for i in raw_input().split()]
querys = [int(i) for i in raw_input().split()]
print answer(querys, A, B)