Problem:


Score : 500 points

Problem Statement

There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i.
Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

Notes

The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.

If N is odd, the median is x_{(N+1)/2};

if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the answer.

Sample Input 1

2
1 2
2 3

Sample Output 1

3

If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};

if X_1 = 1 and X_2 = 3, the median is 2;

if X_1 = 2 and X_2 = 2, the median is 2;

if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.

Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.

Sample Input 2

3
100 100
10 10000
1 1000000000

Sample Output 2

9991



Sample input:
2
1 2
2 3


Sample output:
3

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 main():
    N = I()
    ab = []
    odd = False
    if N % 2 == 1:
        odd = True
    for i in range(N):
        ab.append(LI())

    # beginning sort
    beg_ab = sorted(ab, key=lambda x:x[0])
    en_ab = sorted(ab, key=lambda x:x[1])[::-1]
    # even
    if odd:
        l = beg_ab[N//2][0]
        r = en_ab[N//2][1]
        cnt = r - l + 1
    else:
        l1 = beg_ab[(N-1)//2][0]
        l2 = beg_ab[(N-1)//2 + 1][0]

        r1 = en_ab[(N-1)//2][1]
        r2 = en_ab[(N-1)//2 + 1][1]
        cnt = 2 * ((r1+r2)/2 - (l1+l2)/2) + 1
    print(int(cnt))


main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n)]
    min_arr = sorted(ab, key=lambda x: x[0])
    max_arr = sorted(ab, key=lambda x: x[1])
    if n % 2 != 0:
        a = min_arr[n // 2][0]
        b = max_arr[n // 2][1]
        print(b - a + 1)
    else:
        a1 = min_arr[(n - 1) // 2][0]
        b1 = max_arr[(n - 1) // 2][1]
        a2 = min_arr[(n + 1) // 2][0]
        b2 = max_arr[(n + 1) // 2][1]
        print(b1 + b2 - a1 - a2 + 1)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from statistics import median

n = int(input())
x_min = []
x_max = []
for _ in range(n):
    a, b = map(int, input().split())
    x_min.append(min(a, b))
    x_max.append(max(a, b))

print(int((median(x_max)-median(x_min))*2)+1 if n % 2 == 0 else median(x_max)-median(x_min)+1)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
arraya = []
arrayb = []
for i in range(n):
    a,b = map(int, input().split())
    arraya.append(a)
    arrayb.append(b)

min_median = statistics.median(arraya)
max_median = statistics.median(arrayb)
if n%2 == 0:
    print(int((max_median - min_median)//0.5 + 1))
else:
    print(int(max_median - min_median + 1))

Submission status: Accepted

Solution code:
n = int(input())
#a = [list(map(int, input().split())) for _ in range(n)]
start = []
end = []
for i in range(n):
    a,b = map(int, input().split())
    start.append(a)
    end.append(b)
start.sort()
end.sort()
if (n%2==1):
    print(end[n//2]-start[n//2]+1)
else:
    s = start[n//2-1]+start[n//2]
    e = end[n//2-1]+end[n//2]
    print(e-s+1)

Submission status: Accepted

Solution code:
import sys
import math
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, readline().split())
        A.append(a)
        B.append(b)
    A.sort()
    B.sort()
    if N%2==1:
        l = A[N//2]
        r = B[N//2]
        print(r-l+1)
    else:
        l1 = A[N//2-1]
        r1 = B[N//2-1]
        l2 = A[N//2]
        r2 = B[N//2]
        ans = (r2+r1) - (l2+l1) + 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    N = int(input())
    A, B = [0] * N, [0] * N
    l, r = 0, 0
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    A.sort(), B.sort()
    # 中央値の最大値、最小値
    c_min, c_max = 0, 0
    ans = 0

    if(N % 2):
        N -= 1
        c_min = A[(N + 1) // 2]
        c_max = B[(N + 1) // 2]
        ans = c_max - c_min + 1

    else:
        N -= 1
        c_min = (A[N // 2] + A[N // 2 + 1]) / 2
        c_max = (B[N // 2] + B[N // 2 + 1]) / 2
        ans = (c_max - c_min) * 2 + 1

    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
A = []
B = []
N = int(input())
for i in range(N):
    a, b = [int(i) for i in input().split()]
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if N%2==1:
    mi = N//2
    lmed = A[mi]
    rmed = B[mi]
    print(rmed-lmed+1)

if N%2==0:
    mir = N//2
    mil = mir-1
    lmed = (A[mir]+A[mil]) / 2
    rmed = (B[mir]+B[mil]) / 2
    print(int(2*(rmed-lmed)+1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    N = int(input())
    Alist = []; Blist = []
    for _ in range(N):
        A, B = map(int, readline().split())
        Alist.append(A); Blist.append(B)
    Alist.sort()
    Blist.sort()
    i = N//2
    if N%2 == 0:
        medmin = (Alist[i] + Alist[i-1])
        medmax = (Blist[i] + Blist[i-1])
        ans = medmax - medmin + 1
    else:
        ans = Blist[i] - Alist[i] + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[int(x) for x in input().split()] for _ in range(N)]

    if N % 2 == 1:
        ma = []
        mi = []
        for a, b in AB:
            ma.append(max(a, b))
            mi.append(min(a, b))
        ma.sort()
        mi.sort()
        print(ma[N // 2] - mi[N // 2] + 1)
    else:
        ma = []
        mi = []
        for a, b in AB:
            ma.append(max(a, b))
            mi.append(min(a, b))

        ma.sort()
        mi.sort()
        x = (ma[N // 2] + ma[N // 2 - 1]) / 2
        y = (mi[N // 2] + mi[N // 2 - 1]) / 2
        print(int((x - y) / 0.5) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
list_a = []
list_b = []
for i in range(n):
    a,b = (int(x) for x in input().split())
    list_a.append(a)
    list_b.append(b)
list_a.sort()
list_b.sort()

if n%2==0:
    mi = (list_a[int(n/2)]+list_a[int(n/2)-1])/2
    ma = (list_b[int(n/2)]+list_b[int(n/2)-1])/2
    print(int((ma-mi)*2+1))
else:
    mi = list_a[int((n-1)/2)]
    ma = list_b[int((n-1)/2)]
    print(int(ma-mi+1))

Submission status: Accepted

Solution code:
import numpy as np
N =int(input())
A_B = []
for i in range(N):
    A_B.append(list(map(int,input().split())))
if N % 2 == 1:
    A_B = np.array(A_B).T.tolist()
    min_array = A_B[0]
    min_array.sort()
    min_ = min_array[N // 2]
    max_array = A_B[1]
    max_array.sort()
    max_ = max_array[N // 2]
    print(max_ - min_ + 1)
else:
    A_B = np.array(A_B).T.tolist()
    
    min_array = A_B[0]
    min_array.sort()
    min_ = [min_array[N // 2],min_array[N // 2 - 1]]
    max_array = A_B[1]
    max_array.sort()
    max_ = [max_array[N // 2],max_array[N // 2 - 1]]
    print(max_[0] + max_[1] - min_[0] - min_[1] + 1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
ab = [inpl() for _ in range(n)]
ab.sort()
if n%2:
    l = ab[n//2][0]
    ab.sort(key = lambda x:x[1])
    r = ab[n//2][1]
    print(r-l+1)
else:
    l1 = ab[n//2-1][0]
    l2 = ab[n//2][0]
    ab.sort(key = lambda x:x[1])
    r1 = ab[n//2-1][1]
    r2 = ab[n//2][1]
    print((r2+r1)-(l2+l1)+1)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
table = np.array([list(map(int, input().split())) for _ in range(N)])

inf, sup = np.median(table, axis=0)
diff = sup - inf
if N % 2 == 0:
    diff *= 2
print(int(diff + 1))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    mni = (N - 1) // 2
    mxi = mni if N & 1 else mni + 1
    AB.sort(key=lambda x: x[0])
    mmn = (AB[mni][0] + AB[mxi][0]) / 2
    AB.sort(key=lambda x: x[1])
    mmx = (AB[mni][1] + AB[mxi][1]) / 2
    t = 1 if N & 1 else 2
    print(int((mmx - mmn) * t) + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,*ab = map(int,open(0).read().split())
a = sorted(ab[::2])
b = sorted(ab[1::2])
m = (n-1)//2
if n % 2 == 0:
  print(b[m]-a[m]+b[m+1]-a[m+1]+1)
else:
  print(b[m]-a[m]+1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from bisect import bisect_left, bisect_right
n = int(input())
a = [None] * n
b = [None] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
    
a.sort()
b.sort()
thre = n//2 if n%2 else n//2-1
def sub(x):
    # xが含まれうるか
    small = bisect_right(a, x) - 1
    large = n - bisect_left(b, x) - 1
    if small>=thre and large>=thre:
        return True
    else:
        return False
    
l = 0
r = 10**9+1

def mid(l):
    if n%2:
        return l[n//2]
    else:
        return (l[n//2-1]+l[n//2])/2
    
ml = mid(a)
mr = mid(b)

if n%2:
    print(mr - ml + 1)
else:
    print(int(2*mr - 2*ml + 1))

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for _ in range(N):
  a,b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

A.sort()
B.sort()

if N%2 != 0:
  print(B[(N+1)//2-1]-A[(N+1)//2-1]+1)
else:
  print(int((((B[(N)//2-1]+B[(N)//2])/2)-((A[(N)//2-1]+A[(N)//2])/2))*2+1))

Submission status: Accepted

Solution code:
N = int(input())

MIN = []
MAX = []
for i in range(N):
  a,b = map(int,input().split())
  MIN.append(a)
  MAX.append(b)

MIN.sort()
MAX.sort()

if N%2 == 1:#奇数の時
  C = (N+1)//2-1 #3なら2個目なのでIndexは1
  ans = MAX[C]-MIN[C]+1
else:
  C = N//2-1
  D = C+1
  small = (MIN[C]+MIN[D])/2
  big = (MAX[C]+MAX[D])/2
  #print(small,big)
  ans = (big-small)/0.5+1
  ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
A, B = zip(*tuple(tuple(map(int, input().split())) for _ in range(N)))
if N & 1:
    print(median(B) - median(A) + 1)
else:
    print(int((median(B) - median(A)) * 2 + 0.1) + 1)

Submission status: Accepted

Solution code:

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N]

c = [0]*N
d = [0]*N
for i,ab in enumerate(AB):
    a,b = ab
    c[i] = a
    d[i] = b
c.sort()
d.sort(reverse=True)

if N%2:
    L = c[N//2]
    R = d[N//2]
    print(R-L+1)
else:
    L1 = c[N//2-1]
    R1 = d[N//2]
    L2 = c[N//2]
    R2 = d[N//2-1]
    print((R1+R2)-(L1+L2)+1)

Submission status: Accepted

Solution code:
n = int(input())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

a.sort()
b.sort()

if n % 2 == 1:
    mi = a[n // 2]
    ma = b[n // 2]
    print(ma - mi + 1)
    exit()

mi = a[n // 2 - 1] + a[n // 2]
ma = b[n // 2 - 1] + b[n // 2]
print(ma - mi + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


n = readint()
ab = [readints() for i in range(n)]


if n%2==1:
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2+1:
            r = m
        else:
            l = m
    left = r
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2+1:
            l = m
        else:
            r = m
    right = l
    print(right-left+1)
else:
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2:
            r = m
        else:
            l = m
    left1 = r

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2+1:
            r = m
        else:
            l = m
    left2 = r

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2:
            l = m
        else:
            r = m
    right1 = l

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2+1:
            l = m
        else:
            r = m
    right2 = l
    ans = 0
    ans += right2+right1 - left2-left1 + 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] *N
B = [0]*N
for i in range(N):
    a, b = map(int,input().split())
    A[i] = a
    B[i] = b
A = sorted(A)
B = sorted(B)
if N %2 ==1:
    M = (N+1)//2
    left = A[M-1]
    right = B[-M]
    ans = right - left +1
else:
    M1 = N//2
    M2 = M1+1
    left1 = A[M1-1]
    right1 =B[-M1]
    left2 = A[M2-1]
    right2  =B[-M2]
    ans = right2 + right1 -left1-left2+1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
A=sorted(A)
B=sorted(B)
if N%2==0:
  m=A[N//2]+A[N//2-1]
  M=B[N//2]+B[N//2-1]
  print(M-m+1)
else:
  m=A[N//2]
  M=B[N//2]
  print(M-m+1)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
B = [0]*N 
for i in range(N):
    s,t = map(int,input().split())
    A[i] = s
    B[i] = t
A.sort()
B.sort()
if N%2 == 1:
    a = A[(N-1)//2]
    b = B[(N-1)//2]
    print(b-a+1)
if N%2 == 0:
    a = A[N//2 - 1] + A[N//2]
    b = B[N//2 - 1] + B[N//2]
    print(b-a+1)

Submission status: Accepted

Solution code:
import statistics

N = int(input())
a = []
b = []
for i in range(N):
    A,B = map(int, input().split())
    a.append(A)
    b.append(B)

a2 = statistics.median(a)
b2 = statistics.median(b)

if N % 2 == 0:
    c = (b2-a2)/0.5 + 1
    print(int(c))
else:
    print(b2-a2+1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
import numpy as np
kx = np.array(read().split(),np.int32)
a = kx[::2]
b = kx[1::2]
a.sort()
b.sort()
if n%2 == 1:
  L = a[n//2]
  R = b[n//2]
  ans = R-L+1
else:
  LL = a[n//2-1]
  LR = b[n//2-1]
  RL = a[n//2]
  RR = b[n//2]
  ans = RR+LR-LL-RL+1
print(ans)

Submission status: Accepted

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

N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
    if N % 2 == 0:
        A[i] *= 2
        B[i] *= 2
A.sort()
B.sort()
if N % 2 == 1:
    print(B[N//2] - A[N//2] + 1)
else:
    print((B[N//2-1] + B[N//2] - A[N//2-1] - A[N//2]) // 2 + 1)

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
  x,y = map(int,input().split())
  a.append(x)
  b.append(y)
a.sort()
b.sort()
if n % 2 == 1:
  print(b[n//2] - a[n//2] + 1)
else:
  print(b[n//2]+b[n//2-1]-a[n//2]-a[n//2-1]+1)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for i in range(N):
  Anew, Bnew = map(int,input().split())
  A.append(Anew)
  B.append(Bnew)
A.sort()
B.sort()
if N % 2 == 0:
  min = (A[N//2-1] + A[N//2]) / 2
  max = (B[N//2-1] + B[N//2]) / 2
  print(int((max-min)*2+1))
else:
  min = (A[(N-1)//2])
  max = (B[(N-1)//2])
  print(max-min+1)

Submission status: Accepted

Solution code:
## coding: UTF-8
import statistics
#import math

N = int(input())
#lq = [list(map(int, input().split())) for _ in range(N)]
#print(lq)

A = []
B = []
for i in range(N):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)
#print(A)
#print(B)

#l = [10, 1, 3, 7, 1]

#median = statistics.median(l)
#print(median)

if(N%2 == 1):
    lowest = statistics.median(A)
    highest = statistics.median(B)
    ans = highest - lowest + 1
else:
    lowest = statistics.median(A)
    highest = statistics.median(B)
    ans = (2 * highest) - (2 * lowest) + 1

print(int(ans))

Submission status: Accepted

Solution code:
n=int(input())
ar=[list(map(int,input().split())) for i in range(n)]
low=[ar[i][0] for i in range(n)]
high=[ar[i][1] for i in range(n)]
low.sort()
high.sort()
if n%2==1:
    print(high[n//2]-low[n//2]+1)
else:
    l=(low[n//2]+low[n//2-1])/2
    h=(high[n//2]+high[n//2-1])/2
    print(int((h-l)*2)+1)

Submission status: Accepted

Solution code:
n=int(input())
l1=[]
l2=[]
for i in range(n):
    a,b=map(int,input().split())
    l1.append(a)
    l2.append(b)
l1.sort()
l2.sort()
if n%2==0:
    low=l1[n//2]+l1[n//2-1]
    high=l2[n//2]+l2[n//2-1]
    print(high-low+1)
else:
    low=l1[n//2]
    high=l2[n//2]
    print(high-low+1)

Submission status: Accepted

Solution code:
N=int(input())

A=[]
B=[]
for k in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
    
if N%2==1:
    mA=A[(N-1)//2]
    mB=B[(N-1)//2]
    print(mB-mA+1)
else:
    nA=A[N//2]+A[N//2-1]
    nB=B[N//2]+B[N//2-1]
    print(nB-nA+1)

Submission status: Accepted

Solution code:
N = int(input())
import numpy as np
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int,input().split())
na = np.median(A)
nb = np.median(B)
if N%2 == 1:
    ans = int(nb - na + 1)
    print(ans)
    exit()
else:
    ans = int(2*(nb - na)) + 1
    print(ans)
    exit()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
A.sort()
B.sort()
if N%2:
    print(B[N//2]-A[N//2]+1)
else:
    a=A[N//2-1]+A[N//2]
    b=B[N//2-1]+B[N//2]
    print(b-a+1)

Submission status: Accepted

Solution code:
import statistics

n = int(input())
a = []
b = []

for i in range(n):
  _a, _b = map(int, input().split())
  a.append(_a)
  b.append(_b)

max_median = statistics.median(b)
min_median = statistics.median(a)
if n % 2 == 0:
  print(int((max_median - min_median) * 2) + 1)
else:
  print(int(max_median - min_median) + 1)

Submission status: Accepted

Solution code:
import math

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]

al = []
bl = []
for a,b in ab:
  al.append(a)
  bl.append(b)
al.sort()
bl.sort()

if n%2==0:
  mn = (al[n//2-1]+al[n//2])/2
  mx = (bl[n//2-1]+bl[n//2])/2
  ans = math.floor((mx-mn)*2+1)
else:
  mn = al[n//2]
  mx = bl[n//2]
  ans = mx-mn+1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = []
B = []

for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if n % 2 == 0:
    minimum = (A[n//2 - 1] + A[n//2]) // 2
    mini_minus = (A[n//2 - 1] + A[n//2]) % 2
    maximum = (B[n//2 - 1] + B[n//2]) // 2
    maxim_add = (B[n//2 - 1] + B[n//2]) % 2

    ans = (maximum - minimum) * 2 + 1 - mini_minus + maxim_add

else:
    minimum = A[n//2]
    maximum = B[n//2]
    ans = maximum - minimum + 1

print(ans)

Submission status: Accepted

Solution code:
import statistics

n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
am = statistics.median(A)
bm = statistics.median(B)
#print(am, bm)
if n % 2 == 0:
    print(int(bm * 2 - am * 2 + 1))
else:
    print(int(bm - am + 1))

Submission status: Accepted

Solution code:
N=int(input())

min_x=[]
max_x=[]
for _ in range(N):
    A,B=map(int,input().split())
    min_x.append(A)
    max_x.append(B)

min_x.sort()
max_x.sort()

if N%2==0:
    center=N//2
    min_tmp=(min_x[center]+min_x[center-1])
    max_tmp=(max_x[center]+max_x[center-1])
    print(max_tmp-min_tmp+1)
else:
    center=N//2
    print(max_x[center]-min_x[center]+1)

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
   ai,bi = [int(j) for j in input().split()]
   a.append(ai)
   b.append(bi)
a.sort()
b.sort()
if n == 1:
   ans = b[0] - a[0] + 1
elif n % 2 == 1:
   tg = (n+1) // 2
   ans = b[-tg] - a[tg-1] + 1
else:
   tg = n//2
   ans = b[-tg] + b[-tg-1] - a[tg-1] - a[tg] +1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
import statistics
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=[lmp() for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(n):
    a[i]=l[i][0]
    b[i]=l[i][1]
ma=statistics.median(a)
mb=statistics.median(b)
if n%2==0:
    print(int((mb-ma)*2+1))
else:
    print(int((mb-ma)+1))

Submission status: Accepted

Solution code:
n = int(input())
A = []
B = []
for _ in range(n):
    a,b = map(int,input().split())
    A += [a]
    B += [b]
A.sort()
B.sort()
if n % 2 == 1:
    print(B[n//2]-A[n//2]+1)
else:
    a1 = A[n//2-1]
    a2 = A[n//2]
    b1 = B[n//2-1]
    b2 = B[n//2]
    print(b2+b1-a2-a1+1)

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion

N = ri()
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = ri_()
A.sort()
B.sort()
if N % 2 == 1:
    ans = B[(N - 1) // 2] - A[(N - 1) // 2] + 1
else:
    ans = (B[N // 2 - 1] + B[N // 2]) - (A[N // 2 - 1] + A[N // 2]) + 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
list = [list(map(int,input().split())) for i in range(N)]
if N%2 == 1:
  list.sort()
  #print(list)
  m = list[(N+1)//2-1][0]
  #print('m',m)
  list.sort(key=lambda x: x[1])
  #print(list)
  M = list[(N+1)//2-1][1]
  #print('M',M)
  print(M-m+1)
else:
  list.sort()
  m = list[N//2-1][0]+list[N//2][0]
  list.sort(key=lambda x: x[1])
  M = list[N//2-1][1]+list[N//2][1]
  print(M-m+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
p=[]
q=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([2*a,2*b])
    p.append(2*a)
    q.append(2*b)
p.sort()
q.sort()
if n%2==0:
    al=(p[n//2]+p[n//2-1])//2
    ar=(q[n//2]+q[n//2-1])//2
else:
    al=p[n//2]//2
    ar=q[n//2]//2
print(ar-al+1)

Submission status: Accepted

Solution code:
n = int(input())
aa = [0]*n
bb = [0]*n
for i in range(n):
    aa[i], bb[i] = map(int, input().split())

def get_2med(arr):
    m = len(arr)
    ar = sorted(arr)
    if m%2 == 0:
        return ar[m//2-1] + ar[m//2]
    else:
        return ar[(m+1)//2-1]
    
minmed = get_2med(aa)
maxmed = get_2med(bb)
print(maxmed - minmed + 1)

Submission status: Accepted

Solution code:
N=int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
a,b = zip(*ab)
res = 0
ma = max(b)+1

def solve_left(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2:
        return False
    return True

def solve_right(idx):
    right = sum([1 for l,r in ab if idx>r])
    if right > N//2:
        return False
    return True
def solve_left2(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2-1:
        return False
    return True

def solve_right2(idx):
    right = sum([1 for l,r in ab if idx>r])
    if right > N//2-1:
        return False
    return True

ok = ma
ng = 0
while abs(ok-ng) > 1:
    cnt = (ok + ng) // 2
    if solve_left(cnt):
        ok = cnt
    else:
        ng = cnt
res_left = ok

ok = 0
ng = ma
while abs(ok-ng) > 1:
    cnt = (ok + ng) // 2
    if solve_right(cnt):
        ok = cnt
    else:
        ng = cnt
res_right = ok

if N%2==0:
    ok = ma
    ng = 0
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve_left2(cnt):
            ok = cnt
        else:
            ng = cnt
    res_left2 = ok
    
    ok = 0
    ng = ma
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve_right2(cnt):
            ok = cnt
        else:
            ng = cnt
    res_right2 = ok

if N%2==1:
    res = (res_right-res_left) + 1
else:
    # print((res_left,res_left2),(res_right,res_right2))
    res = (res_right+res_right2)-(res_left+res_left2) + 1
print(res)

Submission status: Accepted

Solution code:
import statistics
n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

median_min=statistics.median(A)
median_max=statistics.median(B)

if n%2!=0:
    ans=int(median_max-median_min+1)
else:
    ans=int(2*median_max-2*median_min+1)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []

for i in range(n):
    aa,bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

a.sort()
b.sort()

if n%2 == 1:
    p = a[n//2]
    q = b[n//2]
    ans = q - p + 1

else:
    p1 = a[n//2 -1]
    p2 = a[n//2]
    q1 = b[n//2]
    q2 = b[n//2 - 1]
    p = (p1+p2)*5
    q = (q1+q2)*5 
    ans = (q-p)//5 + 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
if N % 2 == 0:
    j = N // 2
    i = j - 1
    med1_by_2 = A[i] + A[j]
    med2_by_2 = B[i] + B[j]
    ans = med2_by_2 - med1_by_2 + 1
else:
    i = N // 2
    med1 = A[i]
    med2 = B[i]
    ans = med2 - med1 + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
from decimal import Decimal

mod = 10 ** 9 + 7
INF = 10 ** 13
sys.setrecursionlimit(2147483647)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n = I()
A = []
B = []
for _ in range(n):
    a, b = LI()
    A += [a]
    B += [b]

A.sort()
B.sort()
if n % 2:
    print(B[n // 2] - A[n // 2] + 1)
else:
    print((B[n // 2] + B[n // 2 - 1]) - (A[n // 2] + A[n // 2 - 1]) + 1)

Submission status: Accepted

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

N=int(input())
K=[tuple(map(int,input().split())) for i in range(N)]

if N%2==1:
    
    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MIN=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MAX=OK

    print(MAX-MIN+1)

else:
    
    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MIN0=OK

    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2:
                OK=mid
                break
        else:
            NG=mid

    MIN1=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MAX0=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2:
                OK=mid
                break
        else:
            NG=mid

    MAX1=OK

    #print(MIN0,MIN1,MAX0,MAX1)

    print(int(((MAX1+MAX0)/2-(MIN1+MIN0)/2)*2+1))