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:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n=int(input())
    l,r=[],[]
    for _ in range(n):
        u,v=map(int,input().split())
        l.append(u)
        r.append(v)
    l.sort()
    r.sort()
    u,v=0,0
    if n%2:
        u,v=l[n//2],r[n//2]
    else:
        u,v=l[n//2]+l[n//2-1],r[n//2]+r[n//2-1]
    print(v-u+1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    g = LIR(n)
    if n&1:
        g.sort()
        l = g[n>>1][0]
        g.sort(key = lambda x:x[1])
        r = g[n>>1][1]
        print(r-l+1)
    else:
        g.sort()
        l = g[(n>>1)-1][0]+g[(n>>1)][0]
        g.sort(key = lambda x:x[1])
        r = g[n>>1][1]+g[(n>>1)-1][1]
        print(r-l+1)
    # ans = set()
    # # for i in range(g[0][0],g[0][1]+1):
    # #     for j in range(g[1][0],g[1][1]+1):
    # #         for k in range(g[2][0],g[2][1]+1):
    # #             p = [i,j,k]
    # #             p.sort()
    # #             ans.add(p[1])
    # for i in range(g[0][0],g[0][1]+1):
    #     for j in range(g[1][0],g[1][1]+1):
    #         ans.add((i+j)/2)
    # ans = list(ans)
    # ans.sort()
    # print(len(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
AB = [tuple(map(int,input().split())) for i in range(n)]
A = [ai for ai,bi in AB]
B = [bi for ai,bi in AB]
A.sort()
B.sort()
if n % 2 == 0:
  aa = (A[n//2-1]+A[n//2]) # 実際はこれの二分の１
  bb = (B[n//2-1]+B[n//2])
  print(bb-aa+1)

else:
  aa = (A[n//2]) # 実際はこれの二分の１
  bb = (B[n//2])
  print(bb-aa+1)

# print(aa,bb)
# minx,maxx=0,0
# for ai,bi in AB:
#   minx += ai
#   maxx += bi

Submission status: Accepted

Solution code:
n = int(input())
a, b = [], []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
a.sort()
b.sort()
if n & 1:
    print(b[n // 2] - a[n // 2] + 1)
else:
    a = list(map(lambda x: x * 2, a))
    b = list(map(lambda x: x * 2, b))
    print((b[n // 2 - 1] + b[n // 2]) // 2 
            - (a[n // 2 - 1] + a[n // 2]) // 2 + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]", B: "List[int]"):
    a = A
    b = B
    a.sort()
    b.sort()
    if N % 2 == 0:
        ma = (a[N // 2 - 1] + a[N // 2]) / 2
        mb = (b[N // 2 - 1] + b[N // 2]) / 2
        ret = mb * 2 - ma * 2 + 1
    else:
        ma = (a[N // 2]) / 2
        mb = (b[N // 2]) / 2
        ret = mb * 2 - ma * 2 + 1
    print(int(ret))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for i in range(N)]
A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]

A.sort()
B.sort()

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

Submission status: Accepted

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

if n % 2 == 1:
    a_median = a[(n - 1) // 2]
    b_median = b[(n - 1) // 2]
    # print(a_median, b_median)
    ans = b_median - a_median + 1
else:
    a_median = (a[n // 2 - 1] + a[n // 2])
    b_median = (b[n // 2 - 1] + b[n // 2])
    # print(a_median, b_median)
    ans = b_median - a_median + 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    t = 1
    if N%2 == 0:
        t = 2
    AB = [ tuple( map( lambda x: int(x)*t, input().split())) for _ in range(N)]
    A = [ab[0] for ab in AB]
    B = [ab[1] for ab in AB]
    A.sort()
    B.sort()
    if t == 1:
        m = A[N//2]
        M = B[N//2]
    else:
        m = (A[N//2-1]+A[N//2])//2
        M = (B[N//2-1]+B[N//2])//2
    print(M-m+1)
if __name__ == '__main__':
    main()

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:
    mid_min = a[n//2]
    mid_max = b[n//2]
    print(mid_max-mid_min+1)
else:
    mid_min = (a[n//2-1]+a[n//2])/2
    mid_max = (b[n//2-1]+b[n//2])/2
    print(int((mid_max-mid_min)*2)+1)

Submission status: Accepted

Solution code:
n = int(input())

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

al = []
bl = []

for a,b in abl:
    al.append(a)
    bl.append(b)

al = sorted(al)
bl = sorted(bl)
if n % 2 == 0:
    min_a = (al[n//2-1] + al[n//2]) / 2
    max_a = (bl[n//2-1] + bl[n//2]) / 2
else:
    min_a = al[(n-1)//2]
    max_a = bl[(n-1)//2]

if n % 2 == 0:
    print(int((max_a - min_a) * 2 + 1))
else:
    print(max_a - min_a + 1)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    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 == 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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

def main():
    n = ii()
    l = []
    r = []
    for i in range(n):
        a, b = mi()
        l.append(2 * a)
        r.append(2 * b)
    # print(l)
    l.sort()
    r.sort()
    if n % 2 == 0:
        ll = (l[n // 2] + l[n // 2 - 1]) // 2
        rr = (r[n // 2] + r[n // 2 - 1]) // 2
    else:
        ll = l[n // 2]
        rr = r[n // 2]
    # print(ll, rr)
    if n % 2 == 0:
        print(rr - ll + 1)
    else:
        print(rr // 2 - ll // 2 + 1)
    return

if __name__ == "__main__":
    main()

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:
    l = A[N // 2]
    r = B[N // 2]
    print(r - l + 1)
else:
    l2 = A[N // 2 - 1] + A[N // 2]
    r2 = B[N // 2 - 1] + B[N // 2]
    print(r2 - l2 + 1)

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)
if N%2==1:
    n = N//2
    print(sorted(B, reverse=True)[n]-sorted(A)[n]+1)
    exit()
l, r = (N-2)//2, N//2
A.sort()
B.sort()
print(-A[r]-A[l]+B[r]+B[l]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]", B: "List[int]"):
    for i, a in enumerate(A):
        b = B[i]
    ca = sorted(A)

    def get_middle(arr):
        if len(arr) % 2 == 1:
            return arr[(len(arr)) // 2]
        return (arr[len(arr) // 2 - 1] + arr[len(arr) // 2]) / 2

    cb = sorted(B)
    min_ = (get_middle(ca))
    max_ = (get_middle(cb))
    if N % 2:
        print(max_ - min_ + 1)
    else:
        print(int(2 * max_ - 2 * min_ + 1))

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

alist=sorted(alist)
blist=sorted(blist)

if n%2==1:
    center=(n-1)//2
    answer=blist[center]-alist[center]+1
    print(answer)
else:
    #print(alist, blist)
    mae=(alist[(n//2)-1]+alist[(n//2)])/2
    ato=(blist[(n//2)-1]+blist[(n//2)])/2
    #print(mae, ato)
    print(int((ato-mae)*2+1))

Submission status: Accepted

Solution code:
import statistics
n=int(input())
a=[0 for _ in range(n)]
b=[0 for _ in range(n)]
for i in range(n):
	a[i],b[i] = map(int,input().split())
#やさしい
#つまりは, n=奇数のとき x_((n+1)//2)の値
#つまりは, n=偶数のとき x_(n//2)+x_(n//2+1)の値
#がどのくらいあるかを求める

#さすがに全探索はヤバイ
#奇数→すっっくない。中間として存在する範囲すべてをとりうるか？
ans = 0
if n % 2 == 1:
	ans = statistics.median(b)-statistics.median(a)+1
else:
	ans = int(statistics.median(b)*2-statistics.median(a)*2+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.sort()
B.sort()

if N % 2 == 1:
    am = A[N//2]
    bm = B[N//2]

    print (bm-am+1)

else:
    am = (A[N//2] + A[N//2-1])/2
    bm = (B[N//2] + B[N//2-1])/2

    print ( int((bm-am)/0.5) + 1)

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, B = sorted(A), sorted(B)
m1 = A[N//2] + A[(N-1)//2]
m2 = B[N//2] + B[(N-1)//2]
print((m2 - m1) // (N % 2 + 1) + 1)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    A = [a for a, _ in AB]
    B = [b for _, b in AB]
    A.sort()
    B.sort()
    if N & 1:
        return B[N // 2] - A[N // 2] + 1
    return (B[N // 2] + B[N // 2 - 1]) - (A[N // 2] + A[N // 2 - 1]) + 1

print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N):
  l, r = map(int, input().split())
  a.append((l, r))
a.sort()
X = 0
if N % 2: X = a[N // 2][0]
else: X = (a[N // 2 - 1][0] + a[N // 2][0]) / 2
a.sort(key = lambda x: x[1])
Y = 0
if N % 2: Y = a[N // 2][1]
else: Y = (a[N // 2 - 1][1] + a[N // 2][1]) / 2

if N % 2: print(Y - X + 1)
else: print(int(Y * 2 - X * 2 + 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())
ab = list(map(int,read().split()))
a = ab[::2]
b = ab[1::2]
a.sort()
b.sort()

if(n%2==1):
    n_min = a[n//2]
    n_max = b[n//2]
    ans = n_max-n_min+1
else:
    n_min = a[n//2 -1] + a[n//2]
    n_max = b[n//2 -1] + b[n//2]
    ans = n_max-n_min+1

print(ans)

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=LL(n)
l.sort()
if n%2==1:
    a,b=l[n//2]
    l.sort(key=lambda x:x[1])
    c,d=l[n//2]
    print(d-a+1)
else:
    l.sort()
    a,_=l[n//2-1]
    b,_=l[n//2]
    l.sort(key=lambda x:x[1])
    _,c=l[n//2-1]
    _,d=l[n//2]
    print(c+d-a-b+1)

Submission status: Accepted

Solution code:
n = int(input())

mins = []
maxs = []

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

mins.sort()
maxs.sort()


if n % 2 == 1:
    mid = n // 2
    print(maxs[mid] - mins[mid] + 1)

else:
    mid1 = n//2
    mid2 = mid1-1
    smallest = mins[mid1] + mins[mid2]
    largest = maxs[mid1] + maxs[mid2]
    print(largest - smallest + 1)

Submission status: Accepted

Solution code:
n=int(input())
aa=[]
bb=[]
for _ in range(n):
  a,b=map(int,input().split())
  aa.append(a)
  bb.append(b)
aa.sort()
bb.sort()
if n%2==1:
  print(bb[n//2]-aa[n//2]+1)
else:
  am=aa[n//2]+aa[n//2-1]
  bm=bb[n//2]+bb[n//2-1]
  print(bm-am+1)

Submission status: Accepted

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

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 == 1:
    m = A[N//2]; M = B[N//2]
    print(M-m+1)
else:
    m1 = A[N//2-1]; m2 = A[N//2]
    M1 = B[N//2-1]; M2 = B[N//2]
    ans = M1 + M2 - (m1+m2) + 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
l,r = list(zip(*ab))
l = list(l)
r = list(r)
l.sort()
r.sort()
if n%2:
  print((r[n//2]-l[n//2])+1)
else:
  print(((r[n//2-1]+r[n//2])-(l[n//2-1]+l[n//2]))+1)

Submission status: Accepted

Solution code:
from statistics import median

la = []
lb = []
for _ in range(int(input())):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)

ma = median(la)
mb = median(lb)
if len(la) % 2:
    print(int((mb - ma) + 1))
else:
    print(int(2 * (mb - ma) + 1))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
AB = np.array(read().split(), np.int64)

A = AB[::2]
B = AB[1::2]

A.sort()
B.sort()

if N % 2 == 0:
    n = N // 2
    med1 = A[n - 1] + A[n]
    med2 = B[n - 1] + B[n]
    x = med2 - med1 + 1
else:
    n = N // 2
    med1 = A[n]
    med2 = B[n]
    x = med2 - med1 + 1

print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
l.sort()
if n%2:
	m=l[n//2][0]
else:
	m=(l[n//2-1][0]+l[n//2][0])/2
l.sort(key=lambda x:-x[1])
if n%2:
	M=l[n//2][1]
else:
	M=(l[n//2-1][1]+l[n//2][1])/2
if n%2:
	print(M-m+1)
else:
	print(int(2*(M-m)+1))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    if n % 2 == 1:
        min_a = sorted([a for a, b in ab])[n//2]
        max_a = sorted([b for a, b in ab])[n//2]
        print(max_a-min_a+1)
    else:
        min_a = sum(sorted([a for a, b in ab])[n//2-1:n//2+1])*2
        max_a = sum(sorted([b for a, b in ab])[n//2-1:n//2+1])*2
        print((max_a-min_a+2)//2)


main()

Submission status: Accepted

Solution code:
N = int(input())

ranges = [tuple(map(int,input().split())) for _ in range(N)]
A = sorted(a for a,b in ranges)
B = sorted(b for a,b in ranges)
if N % 2 == 0:
    a = A[N//2-1]+A[N//2]
    b = B[N//2-1]+B[N//2]
    print(b-a+1)
else:
    a = A[N//2]
    b = B[N//2]
    print(b-a+1)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
def md(x):
    u = sorted(x)
    if len(u) % 2 == 0:
        return u[len(u) // 2] + u[len(u) // 2 - 1]
    else:
        return u[len(u) // 2]
u, v = md(a), md(b)
print(v - u + 1)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
a.sort()
b.sort()
if n & 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:
import sys
input=sys.stdin.readline

def solve_odd(n,AB):
    AB.sort()
    median_min=AB[n//2][0]
    AB.sort(key=lambda x: x[1])
    median_max=AB[n//2][1]
    #print(median_max,median_min)
    return max(0,median_max-median_min+1)

def solve_even(n,AB):
    AB.sort()
    median_min=AB[n//2-1][0]+AB[n//2][0]
    AB.sort(key=lambda x: x[1])
    median_max=AB[n//2-1][1]+AB[n//2][1]
    #print(median_max,median_min)
    return max(0,median_max-median_min+1)

def main():
    n=int(input())
    AB=[list(map(int,input().split())) for _ in range(n)]
    if n%2==0:
        ans=solve_even(n,AB)
    else:
        ans=solve_odd(n,AB)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n = ni()
a = list(map(int, readall().split()))
l = a[::2]
h = a[1::2]
l.sort()
h.sort()
ml = l[n//2] if n&1 else (l[n//2] + l[n//2-1])
mh = h[n//2] if n&1 else (h[n//2] + h[n//2-1])
print(mh - ml + 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = []
b = []
for i in range(n):
    u, v = na()
    a.append(u)
    b.append(v)

if n % 2 == 1:
    a.sort()
    b.sort()
    print(b[n//2]-a[n//2]+1)
else:
    a.sort()
    b.sort()
    print((b[n//2]+b[n//2-1])-(a[n//2]+a[n//2-1])+1)

Submission status: Runtime Error

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

array1.sort()
array2.sort()

if N % 2 == 0:
    min = array1[N//2]+array1[N//2+1]
    max = array2[N//2]+array2[N//2+1]
    print(max-min+1)
else:
    min = array1[N//2]
    max = array2[N//2]
    print(max-min+1)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(int i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")




int main() {
	vector<ll> a, b;
	int N;
	cin >> N;
	REP(i, 0, N) {
		ll a_, b_;
		cin >> a_ >> b_;
		a.push_back(a_);
		b.push_back(b_);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if (N % 2 == 1) {
		PRI(b[N / 2] - a[N / 2] + 1);
	}
	else {
		PRI((b[N / 2 - 1] + b[N / 2]) - (a[N / 2 - 1] + a[N / 2]) + 1);
	}
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def is_median(k, xl, is_odd):
	over = 0
	under = 0
	inner = 0
	same = 0
	for a,b in xl:
		if b < k:
			under+=1
		elif k<a:
			over+=1
		elif a==k and b == k:
			same+=1
		else:
			inner+=1
	
	if abs(under-over) < same+inner:
		return 0
	else:
		return 1 if under > over else -1

def main2():
	n = int(input())
	#b , c = tin()
	xl=[]
	for _ in range(n):
		a,b = tin()
		xl.append((a,b))
	#s = input()
	min_v=0
	max_v=mod
	for a,b in xl:
		min_v=min(min_v, a)
		max_v=max(max_v, b)
	
	d = 1 if n % 2 == 0 else 1/2
	
	k_max_ok = min_v
	k_max_ng = max_v
	while k_max_ng - k_max_ok > d:
		pass
	
	k_min_ok = min_v
	
def main():
	n = int(input())
	al=[]
	bl=[]
	for i in range(n):
		a,b = tin()
		al.append(a)
		bl.append(b)
		
	al.sort()
	bl.sort()
	
	if n % 2 == 1:
		pos = ((n + 1) // 2) - 1
		d = bl[pos] - al[pos] + 1
		return d
	else:
		pos_l = ((n) // 2) - 1
		pos_r = pos_l + 1
		
		if al[pos_r] < bl[pos_l]:
			r = bl[pos_l] - al[pos_l] + bl[pos_r] - al[pos_r] + 1 - max(0, al[pos_r]-bl[pos_l])
		else:
			return 1/0
			r = bl[pos_l] - al[pos_l] + bl[pos_r] - al[pos_r] + 1 - max(0, al[pos_r]-bl[pos_l])
		return r
		
			
		
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def is_median(k, xl, is_odd):
	over = 0
	under = 0
	inner = 0
	same = 0
	for a,b in xl:
		if b < k:
			under+=1
		elif k<a:
			over+=1
		elif a==k and b == k:
			same+=1
		else:
			inner+=1
	
	if abs(under-over) < same+inner:
		return 0
	else:
		return 1 if under > over else -1

def main2():
	n = int(input())
	#b , c = tin()
	xl=[]
	for _ in range(n):
		a,b = tin()
		xl.append((a,b))
	#s = input()
	min_v=0
	max_v=mod
	for a,b in xl:
		min_v=min(min_v, a)
		max_v=max(max_v, b)
	
	d = 1 if n % 2 == 0 else 1/2
	
	k_max_ok = min_v
	k_max_ng = max_v
	while k_max_ng - k_max_ok > d:
		pass
	
	k_min_ok = min_v
	
def main():
	n = int(input())
	al=[]
	bl=[]
	for i in range(n):
		a,b = tin()
		al.append(a)
		bl.append(b)
		
	al.sort()
	bl.sort()
	
	if n % 2 == 1:
		pos = ((n + 1) // 2) - 1
		d = bl[pos] - al[pos] + 1
		return d
	else:
		return 1/0
		pos_l = ((n) // 2) - 1
		pos_r = pos_l + 1
		min_l=al[pos_lu]
		
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
N = int(input())
T = [0] * (10**6+10)

nax = 0
for i in range(N):
    A, B = map(int, input().split())
    T[A] += 1
    T[B+1] -= 1
    nax = max(nax, B)

for i in range(1, nax+1):
    T[i] += T[i-1]

cnt = 0
for i in range(nax-1):
    if T[i] > 0:
        cnt+=1
        if T[i+1] > 0:
            cnt += N-1
else:
    if T[nax-1] > 0:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
C = {}
for i in range(N):
    a,b = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
    if b not in C:
        C[b] = 0
    C[b] += 1
C = sorted(list(C.keys()))
if N%2==1:
    k = (N+1)//2
    a = C[k-2]
    b = C[-(k-1)]
    print(b-a+1)
else:
    k = N//2
    a = C[k-2]
    a1 = C[k-1]
    b = C[-(k-1)]
    b1 = C[-(k-1)-1]
    print(b+b1-a-a1+1)

Submission status: Runtime Error

Solution code:
n=int(input(""))
a=[]
b=[]
for i in range(n):
    cc=input("").split(" ")
    a+=[int(cc[0])]
    b+=[int(cc[1])]
s=0
a.sort()
b.sort()
if (n%2==0):
    s=(a[n/2]+a[n/2-1]-b[n/2]-b[n/2-1])/2
else:
    s=a[int((n-1)/2)]-b[int((n-1)/2)]
print(-s+1)

Submission status: Runtime Error

Solution code:
n=int(input(""))
a=[]
b=[]
for i in range(n):
    cc=input("").split(" ")
    a+=[int(cc[0])]
    b+=[int(cc[1])]
s=0
a.sort()
b.sort()
if (n%2==0):
    s=(a[n/2]+a[n/2-1]-b[n/2]-b[n/2-1])/2
else:
    s=a[int((n+1)/2)]-b[int((n+1)/2)]
print(-s+1)

Submission status: Runtime Error

Solution code:
n=int(input(""))
a=[]
b=[]
for i in range(n):
    cc=input("").split(" ")
    a+=[int(cc[i])]
    b+=[int(cc[i])]
s=0
a.sort()
b.sort()
if (n%2==0):
    s=(a[n/2]+a[n/2-1]-b[n/2]-b[n/2-1])/2
else:
    s=a[(n+1)/2]-b[(n+1)/2]
print(s+1)

Submission status: Runtime Error

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

if(N%2==1):
  x = A[(N-1)//2]
  y = B[(N-1)//2]
  print(y-x+1)
else:
  x = A[(N//2)+1] + A[N//2]
  y = B[(N//2)+1] + B[N//2]
  print(y-x+1)

Submission status: Runtime Error

Solution code:
from decimal import Decimal

N = Decimal(input())
t = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

if N%2 == 1:
    a_median = a_list[t]
    b_median = b_list[t]
    print(b_median-a_median+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))

Submission status: Runtime Error

Solution code:
N = int(input())
t = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

if N%2 == 1:
    a_med = a_list[t]
    b_median = b_list[t]
    print(b_list-a_list+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))

Submission status: Runtime Error

Solution code:
N = int(input
med = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

if N%2 == 1:
    a_med = a_list[t]
    b_median = b_list[t]
    print(b_list-a_list+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))

Submission status: Runtime Error

Solution code:
from sys import stdin
from statistics import median


def main():
    i = 0
    n = 10**10
    a = []
    b = []
    for line in stdin:
        if i == 0:
            n = int(line)
            i += 1
            continue
        (ai, bi) = line.split()
        a.append(int(ai))
        b.append(int(bi))
        i += 1
        if i > n:
            break

    a_mid = median(a)
    b_mid = median(b)
    if mid_a == mid_b:
        print(1)
        return
    if mid_b - mid_a < 1:
        print(2)
        return
    if n % 2 == 0:
        print(int(b_mid - a_mid) * 2 + 1)
    else:
        print(int(b_mid - a_mid) + 1)

main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
	a_1, b_1 = input().split()
	a.append(int(a_1))
	b.append(int(b_1))
a.sort()
b.sort()
is_odds = n % 2 == 0
a_med = a[(n + 1) // 2 - 1] if not is_odds else (a[n // 2 - 1] + a[n // 2]) / 2
b_med = b[(n + 1) // 2 - 1] if not is_odds else (b[n // 2 - 1] + b[n // 2]) / 2
from_a = a_med if not is_odds else int(a_med * 2)
to_b = b_med if not is_odds else int(b_med * 2)

print(len(list(range(from_a, to_b + 1))))

Submission status: Runtime Error

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

a.sort()
b.sort()

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

Submission status: Runtime Error

Solution code:
N=int(input())
a=[]
b=[]
for i in range(N):
    n,m=input().split()
    a.append(int(n))
    b.append(m)
a.sort()
b.sort()
###if N%2==1:
p=a[0]
sum=0
while p<= b[N-1]:
    i=N-1
    while p > a[i]:
        i -= 1
    x = N-i-1
    i=0
    while p < b[i]:
        i+=1
    y=i
    z=N-x-y
    if((x+z>=int((N+1)/2)) and(y+z>=int((N+1)/2)) and (z>=1)):
        sum+=1
    p +=1
print(p)