Problem:


Score : 1200 points

Problem Statement

There are N apartments along a number line, numbered 1 through N.
Apartment i is located at coordinate X_i.
Also, the office of AtCoder Inc. is located at coordinate S.
Every employee of AtCoder lives in one of the N apartments.
There are P_i employees who are living in Apartment i.

All employees of AtCoder are now leaving the office all together.
Since they are tired from work, they would like to get home by the company's bus.
AtCoder owns only one bus, but it can accommodate all the employees.
This bus will leave coordinate S with all the employees and move according to the following rule:

Everyone on the bus casts a vote on which direction the bus should proceed, positive or negative. (The bus is autonomous and has no driver.) Each person has one vote, and abstaining from voting is not allowed. Then, the bus moves a distance of 1 in the direction with the greater number of votes. If a tie occurs, the bus moves in the negative direction. If there is an apartment at the coordinate of the bus after the move, all the employees who live there get off.

Repeat the operation above as long as there is one or more employees on the bus.

For a specific example, see Sample Input 1.

The bus takes one seconds to travel a distance of 1.
The time required to vote and get off the bus is ignorable.

Every employee will vote so that he himself/she herself can get off the bus at the earliest possible time.
Strictly speaking, when a vote is taking place, each employee see which direction results in the earlier arrival at his/her apartment, assuming that all the employees follow the same strategy in the future.
Based on this information, each employee makes the optimal choice, but if either direction results in the arrival at the same time, he/she casts a vote to the negative direction.

Find the time the bus will take from departure to arrival at the last employees' apartment.
It can be proved that, given the positions of the apartments, the numbers of employees living in each apartment and the initial position of the bus, the future movement of the bus is uniquely determined, and the process will end in a finite time.

Constraints

1 \leq N \leq 10^5

1 \leq S \leq 10^9

1 \leq X_1 < X_2 < ... < X_N \leq 10^9

X_i \neq S ( 1 \leq i \leq N )

1 \leq P_i \leq 10^9 ( 1 \leq i \leq N )

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N S
X_1 P_1
X_2 P_2
:
X_N P_N

Output

Print the number of seconds the bus will take from departure to arrival at the last employees' apartment.

Sample Input 1

3 2
1 3
3 4
4 2

Sample Output 1

4

Assume that the bus moves in the negative direction first.
Then, the coordinate of the bus changes from 2 to 1, and the employees living in Apartment 1 get off.
The movement of the bus after that is obvious: it just continues moving in the positive direction.
Thus, if the bus moves in the negative direction first, the coordinate of the bus changes as 2 → 1 → 2 → 3 → 4 from departure.
The time it takes to get home for the employees living in Apartment 1, 2, 3 are 1, 3, 4 seconds, respectively.

Next, assume that the bus moves in the positive direction first.
Then, the coordinate of the bus changes from 2 to 3, and the employees living in Apartment 2 get off.
Afterwards, the bus starts heading to Apartment 1, because there are more employees living in Apartment 1 than in Apartment 3.
Then, after arriving at Apartment 1, the bus heads to Apartment 3.
Thus, if the bus moves in the positive direction first, the coordinate of the bus changes as 2 → 3 → 2 → 1 → 2 → 3 → 4 from departure.
The time it takes to get home for the employees living in Apartment 1, 2, 3 are 3, 1, 6 seconds, respectively.

Therefore, in the beginning, the employees living in Apartment 1 or 3 will try to move the bus in the negative direction.
On the other hand, the employees living in Apartment 2 will try to move the bus in the positive direction in the beginning.
There are a total of 3 + 2 = 5 employees living in Apartment 1 and 3 combined, which is more than those living in Apartment 2, which is 4.
Thus, the bus will move in the negative direction first, and the coordinate of the bus will change as 2 → 1 → 2 → 3 → 4 from departure.

Sample Input 2

6 4
1 10
2 1000
3 100000
5 1000000
6 10000
7 100

Sample Output 2

21

Since the numbers of employees living in different apartments are literally off by a digit, the bus consistently head to the apartment where the most number of employees on the bus lives.

Sample Input 3

15 409904902
94198000 15017
117995501 7656764
275583856 313263626
284496300 356635175
324233841 607
360631781 148
472103717 5224
497641071 34695
522945827 816241
554305668 32
623788284 22832
667409501 124410641
876731548 12078
904557302 291749534
918215789 5

Sample Output 3

2397671583



Sample input:
3 2
1 3
3 4
4 2


Sample output:
4

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect
from operator import add
def inpl(): return map(int, input().split())


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func
 
    def find(self, i):
        return self.A[i + self.N]
 
    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])
 
    def merge(self, a, b):
        return self.F(a, b)
 
    def total(self):
        return self.A[1]
 
    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1
 
        return res
 

N, S = inpl()
X = [0]
P = [0]
for _ in range(N):
    x, p = inpl()
    X.append(x)
    P.append(p)

P.append(0)
l = bisect(X, S) - 1
x = S
seg = Seg(P, 0, add)
ans = 0

while seg.total():
    L = seg.query(0, l+1)
    R = seg.total() - L
    if L >= R:
        ans += abs(x - X[l])
        seg.update(l, 0)
        x = X[l]
        l -= 1

    else:
        ans += abs(x - X[l+1])
        seg.update(l+1, 0)
        x = X[l+1]
        l += 1

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,s = LI()
    a = [LI() for _ in range(n)]
    x = [_[0] for _ in a]
    p = [_[1] for _ in a]
    if x[0] > s:
        return x[-1] - s
    if x[-1] < s:
        return s - x[0]
    r = 0
    i = 0
    j = n - 1
    d = p[:]
    e = collections.defaultdict(list)
    sk = set()
    while i < j:
        if x[i] > s:
            break
        if x[j] < s:
            break
        if d[i] >= d[j]:
            d[i] += d[j]
            j -= 1
            if j >= 0 and d[j] < d[j+1]:
                d[j] = d[j+1]
                sk.add(i)
        else:
            d[j] += d[i]
            i += 1
            if i < n and d[i] < d[i-1]:
                d[i] = d[i-1]
                sk.add(i)
    t = s
    if i == j:
        r += abs(x[i]-s)
        t = x[i]
        i -= 1
        j += 1
    else:
        if x[i] > s:
            r += abs(x[j]-s)
            t = x[j]
            i -= 1
            j += 1
        else:
            r += abs(x[i]-s)
            t = x[i]
            i -= 1
            j += 1

    while i >= 0 or j < n:
        if i < 0:
            r += abs(x[-1]-t)
            break
        if j >= n:
            r += abs(x[0]-t)
            break
        if i in sk:
            d[i-1] = d[i]
            i-=1
            continue
        if j in sk:
            d[j+1] = d[j]
            J+=1
            continue

        if d[i] >= d[j]:
            r += abs(x[i]-t)
            t = x[i]
            i -= 1
        else:
            r += abs(x[j]-t)
            t = x[j]
            j += 1


    return r



print(main())

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,s = LI()
    a = [LI() for _ in range(n)]
    x = [_[0] for _ in a]
    p = [_[1] for _ in a]
    if x[0] > s:
        return x[-1] - s
    if x[-1] < s:
        return s - x[0]
    r = 0
    i = 0
    j = n - 1
    d = p[:]
    e = collections.defaultdict(list)
    while i < j:
        if x[i] > s:
            break
        if x[j] < s:
            break
        if d[i] >= d[j]:
            d[i] += d[j]
            j -= 1
            if j >= 0 and d[j] < d[j+1]:
                d[j] = d[j+1]
        else:
            d[j] += d[i]
            i += 1
            if i < n and d[i] < d[i-1]:
                d[i] = d[i-1]
    t = s
    if i == j:
        r += abs(x[i]-s)
        t = x[i]
        i -= 1
        j += 1
    else:
        if x[i] > s:
            r += abs(x[j]-s)
            t = x[j]
            i -= 1
            j += 1
        else:
            r += abs(x[i]-s)
            t = x[i]
            i -= 1
            j += 1

    while i >= 0 or j < n:
        if i < 0:
            r += abs(x[-1]-t)
            break
        if j >= n:
            r += abs(x[0]-t)
            break
        if d[i] >= d[j]:
            r += abs(x[i]-t)
            t = x[i]
            i -= 1
        else:
            r += abs(x[j]-t)
            t = x[j]
            j += 1


    return r



print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n, s = f.read_int_list()
    x = [f.read_int_list() for _ in xrange(n)]

    ans = 0
    side = 0
    while True:
        if x[0][0] > s:
            return ans + x[-1][0] - s
        elif x[-1][0] < s:
            return ans + s - x[0][0]
        else:
            if x[0][1] >= x[-1][1]:
                x[0][1] += x[-1][1]
                if side != 1:
                    ans += x[-1][0] - x[0][0]
                side = 1
                x.pop()
            else:
                x[-1][1] += x[0][1]
                if side != -1:
                    ans += x[-1][0] - x[0][0]
                side = -1
                x.pop(0)


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

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)

"""
・両端のマンション → どういうルートをたどっても順序が決まる → 彼らの意見は常に一致するとしてよい
"""

N,S,*XP = map(int,read().split())
X = XP[::2]
P = XP[1::2]

leftN = sum(x<S for x in X)
leftX = X[leftN-1::-1] # 内側から順にもつ
leftP = P[leftN-1::-1] # 内側から順にもつ
rightN = N-leftN
rightX = X[leftN:]
rightP = P[leftN:]

visit = [] # 後ろ側から訪問順
while leftN and rightN:
    p1 = leftP[-1]; x1 = leftX[-1]
    p2 = rightP[-1]; x2 = rightX[-1]
    if p1 < p2:
        visit.append(x1)
        leftP.pop(); leftX.pop(); leftN -= 1
        rightP[-1] = p1 + p2
    else:
        visit.append(x2)
        rightP.pop(); rightX.pop(); rightN -= 1
        leftP[-1] = p1 + p2

if leftN:
    visit += leftX[::-1]
else:
    visit += rightX[::-1]
visit.append(S)

answer = sum(x-y if x>y else y-x for x,y in zip(visit,visit[1:]))
print(answer)

Submission status: Accepted

Solution code:
import numpy as np


def solve(l, r):
    l.reverse()

    stops = []

    if l and r:
        while l and r:
            lx, lp = l.pop()
            rx, rp = r.pop()
            if lp >= rp:
                l.append((lx, lp + rp))
                stops.append(rx)
            else:
                r.append((rx, lp + rp))
                stops.append(lx)

    if l:
        stops.append(l[-1][0])
    else:
        stops.append(r[-1][0])
    stops.append(s)

    return abs(np.diff(np.array(stops, dtype=np.int64))).sum()


n, s = map(int, input().split())
l, r = [], []
for _ in range(n):
    x, p = map(int, input().split())
    if x < s:
        l.append((x, p))
    else:
        r.append((x, p))

print(solve(l, r))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import math
import random
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


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


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(S, X, P):
    X_ = [[P[i], [x]] for i, x in enumerate(X)]
    i = 0
    j = len(X_) - 1
    # while len(X_) != 1:
    while i < j:

        if X_[i][0] >= X_[j][0]:
            X_[i][0] += X_[j][0]
            X_[i][1] += X_[j][1]
            j -= 1
        else:
            X_[j][0] += X_[i][0]
            X_[j][1] += X_[i][1]
            i += 1

    t = 0
    pos = S
    p0 = S
    p1 = S
    for o in X_[i][1]:
        if p0 < o < p1:
            continue

        t += abs(pos - o)
        if o < pos:
            p0 = o
        else:
            p1 = o
        pos = o

    return t


def main():

    N, S = read_int_n()
    X = []
    P = []
    for _ in range(N):
        x, p = read_int_n()
        X.append(x)
        P.append(p)

    # import random
    # N = 100000
    # S = N / 2
    # X = [x + 1 for x in range(N)]
    # P = [random.randint(1, 1000000000) for _ in range(N)]

    print(slv(S, X, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


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


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(S, X, P):
    X_ = [[P[i], [x]] for i, x in enumerate(X)]
    while len(X_) != 1:
        if X_[0][0] >= X_[-1][0]:
            di = -1
            li = 0
        else:
            di = 0
            li = -1
        X_[li][0] += X_[di][0]
        X_[li][1] += X_[di][1]
        X_.pop(di)

    t = 0
    pos = S
    p0 = S
    p1 = S
    for o in X_[0][1]:
        if p0 < o < p1:
            continue

        t += abs(pos - o)
        if o < pos:
            p0 = o
        else:
            p1 = o
        pos = o

    return t


def main():

    N, S = read_int_n()
    X = []
    P = []
    for _ in range(N):
        x, p = read_int_n()
        X.append(x)
        P.append(p)

    print(slv(S, X, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n, s = f.read_int_list()
    x = [f.read_int_list() for _ in xrange(n)]

    ans = 0
    side = 0
    l = 0
    r = n-1
    while True:
        if x[l][0] > s:
            return ans + x[r][0] - s
        elif x[r][0] < s:
            return ans + s - x[l][0]
        else:
            if x[l][1] >= x[r][1]:
                x[l][1] += x[r][1]
                if side != 1:
                    ans += x[r][0] - x[l][0]
                side = 1
                r -= 1
            else:
                x[r][1] += x[l][1]
                if side != -1:
                    ans += x[r][0] - x[l][0]
                side = -1
                l += 1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,s = LI()
    a = [LI() for _ in range(n)]
    x = [_[0] for _ in a]
    p = [_[1] for _ in a]
    if x[0] > s:
        return x[-1] - s
    if x[-1] < s:
        return s - x[0]
    r = 0
    i = 0
    j = n - 1
    d = p[:]
    e = collections.defaultdict(list)
    sk = set()
    while i < j:
        if x[i] > s:
            break
        if x[j] < s:
            break
        if d[i] >= d[j]:
            d[i] += d[j]
            j -= 1
        else:
            d[j] += d[i]
            i += 1
    t = s
    k = sorted(list(zip(d,range(n))), reverse=True)
    lx = rx = s
    for _,i in k:
        if lx <= x[i] <= rx:
            continue
        if lx > x[i]:
            lx = x[i]
        else:
            rx = x[i]
        r += abs(t-x[i])
        t = x[i]


    return r



print(main())