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 statistics
N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
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())
I = [tuple(map(int, input().split())) for _ in range(N)]
As = []
Bs = []
for a, b in I:
	As.append(a)
	Bs.append(b)
As.sort()
Bs.sort()

if N % 2 == 0:
	lows = As[N//2] + As[N//2-1]
	his = Bs[N//2] + Bs[N//2-1]
else:
	lows = As[N//2]
	his = Bs[N//2]

print(his - lows + 1)

Submission status: Accepted

Solution code:
import os

import itertools
import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
A = list(A)
B = list(B)
AB = list(zip(A, B))


def test():
    ranges = (range(a, b + 1) for a, b in AB)
    s = set()
    for X in itertools.product(*ranges):
        s.add(np.median(np.array(X, dtype=float)))
    print(len(s))
    print(list(sorted(s)))


A.sort()
B.sort()


def solve_odd():
    mid = N // 2
    l, r = A[mid], B[mid]
    return r - l + 1


def solve_even():
    mid = N // 2 - 1
    l1, l2 = A[mid:mid + 2]
    r1, r2 = B[mid:mid + 2]
    return r1 + r2 - l1 - l2 + 1
    # print(l1 + l2)
    # print(r1 + r2)
    # print(l1, l2, (l1 + l2) / 2, r1, r2, (r1 + r2) / 2)
    # print(A)
    # print(B)
    # return r - l + 1


if N % 2 == 1:
    ans = solve_odd()
else:
    ans = solve_even()
print(ans)

# test()

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
AB = [ inpl() for _ in range(N) ]
AB.sort()
if N % 2:
    med1 = AB[(N+1)//2-1][0]
else:
    med1 = AB[N//2-1][0] + AB[N//2][0]

AB.sort(key=lambda x: x[1])
if N % 2:
    med2 = AB[(N+1)//2-1][1]
else:
    med2 = AB[N//2-1][1] + AB[N//2][1]

print(med2 - med1 + 1)

Submission status: Accepted

Solution code:
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

lst_min = []
lst_max = []
for i in range(N):
  lst_min.append(lst[i][0])
  lst_max.append(lst[i][1])
lst_min.sort()
lst_max.sort()

if N % 2 == 1: ## 奇数
  median_min = lst_min[(N+1)//2 -1]
  median_max = lst_max[(N+1)//2 -1]
else: ## 偶数
  median_min = (lst_min[N//2 -1] + lst_min[N//2]) / 2.0
  median_max = (lst_max[N//2 -1] + lst_max[N//2]) / 2.0
  
if N % 2 == 1: ## 奇数
  ans = 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 _ in range(n):
  i = input().split()
  a.append(int(i[0]))
  b.append(int(i[1]))
a.sort()
b.sort()
if n%2:
  l = a[n//2]
  h = b[n//2]
  print(h-l+1)
else :
  l = (a[n//2-1]+a[n//2]) / 2
  h = (b[n//2-1]+b[n//2]) / 2
  print(int((h-l)*2) +1)

Submission status: Accepted

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

if(N%2==1):
  print(Bs[N//2] - As[N//2] + 1)
else:
  ans = ( (Bs[N//2-1]+Bs[N//2])/2 - (As[N//2-1]+As[N//2])/2 ) * 2 + 1
  print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
cnd = list(list(map(int, input().split())) for _ in range(n))

a = [0]*n
b = [0]*n

for i in range(n):
    a[i] = cnd[i][0]
    b[i] = cnd[i][1]
    
a.sort()
b.sort()

if n%2 == 1:
    a_cen = a[n//2]
    b_cen = b[n//2]
else:
    a_cen1 = a[n//2 - 1]
    a_cen2 = a[n//2]
    b_cen1 = b[n//2 - 1]
    b_cen2 = b[n//2]
    a_cen = a_cen1 + a_cen2
    b_cen = b_cen1 + b_cen2
    
ans = b_cen - a_cen + 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
aa = []
bb = []
for i in range(N):
    a,b = [int(x) for x in input().split()]
    aa.append(a)
    bb.append(b)
aa.sort()
bb.sort()
if N % 2 != 0:
    print(bb[N//2]-aa[N//2]+1)
else:
    print(bb[N//2]+bb[N//2-1]-aa[N//2]-aa[N//2-1]+1)

Submission status: Accepted

Solution code:
N = int(input())
I = []

for _ in range(N):
  I.append(list(map(int, input().split())))

L = sorted(I)
R = sorted(I, key = lambda x: x[1])

if N%2 == 1:
  x = N//2
  print(R[x][1] - L[x][0] + 1)
else:
  x = N//2
  M = R[x][1] - L[x][0] + 1
  m = R[x-1][1] - L[x-1][0] + 1
  print(M + m - 1)

Submission status: Accepted

Solution code:
import itertools
import copy
from collections import deque
import heapq
n = int(input())
ma = []
mi = []
for i in range(n):
    a,b = map(int,input().split())
    mi.append(a)
    ma.append(b)
mi.sort()
ma.sort()
if n % 2 == 1:
    ans = ma[(n+1)//2-1]-mi[(n+1)//2-1] + 1
else:
    ans = (ma[n//2]+ma[n//2-1]-mi[n//2]-mi[n//2-1])+1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    ab.sort()
    if n & 1:
        ans = ab[n // 2][0]
    else:
        ans = ab[n // 2 - 1][0] + ab[n // 2][0]
        ans /= 2
    ab = list(map(lambda x: x[1], ab))
    ab.sort()
    if n & 1:
        print((ab[n // 2] - ans) + 1)
    else:
        print(int(((ab[n // 2 - 1] + ab[n // 2]) / 2 - ans) * 2 + 1))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
C=[list(map(int,input().split())) for _ in range(N)]

A=[]
B=[]
for i in range(N):
    A.append(C[i][0])
    B.append(C[i][1])

A.sort()
B.sort()

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

print(mB-mA+1)

Submission status: Accepted

Solution code:
import sys
from statistics import median

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    if n % 2:
        am = median(A)
        bm = median(B)
        print(int(abs(bm - am) + 1))
    else:
        A.sort()
        B.sort()
        am = (A[n // 2 - 1] + A[n // 2]) / 2
        bm = (B[n // 2 - 1] + B[n // 2]) / 2
        print(int(abs((bm - am) * 2) + 1))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

A = sorted(A)
B = sorted(B)

if N % 2 == 1:
    ans = B[N//2] - A[N//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:
import sys

def main():
    N = int(input())
    lines = sys.stdin.read().strip().split('\n')
    AB = list(map(lambda l: list(tuple(map(int, l))), map(str.split, lines)))
    AB_by_A = sorted(AB)
    AB_by_B = sorted(AB, key=lambda t: (t[1], t[0]))
    if N % 2 == 1:
        mn = AB_by_A[N//2][0]
        mx = AB_by_B[N//2][1]
        print(mx - mn + 1)
        return
    mn1 = AB_by_A[N//2 - 1][0]
    mn2 = AB_by_A[N//2][0]
    mx1 = AB_by_B[N//2 - 1][1]
    mx2 = AB_by_B[N//2][1]
    mn = mn1 + mn2
    mx = mx1 + mx2
    print(mx - mn + 1)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a_list = []
b_list = []

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

a_list.sort()
b_list.sort()

if n%2==0:
    half = int(n/2)
    first = (a_list[half-1]+a_list[half])/2
    last = (b_list[half-1]+b_list[half])/2
    print(int((last-first)/0.5)+1)
else:
    half = int((n+1)/2)
    print(b_list[half-1]-a_list[half-1]+1)

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]


if n % 2 == 1:
  man = n // 2 + 1
  ab.sort(key=lambda x:x[0])
  ansmin1 = ab[man-1][0]
  ab.sort(key=lambda x:x[1])
  ansmax2 = ab[man-1][1]
  print(ansmax2-ansmin1+1)
else:
  man = n // 2 
  man2 = n // 2 + 1
  ab.sort(key=lambda x:x[0])
  ansmin1 = ab[man-1][0]
  ansmin2 = ab[man2-1][0]
  ab.sort(key=lambda x:x[1])
  ansmax1 = ab[man-1][1]
  ansmax2 = ab[man2-1][1]
  print(ansmax1+ansmax2-ansmin1-ansmin2+1)

Submission status: Accepted

Solution code:
import statistics

N = int(input())
P = [[int(i) for i in input().split()] for _ in range(N)]


left = []
right = []

for i in range(N):
    left.append(P[i][0])
    right.append(P[i][1])

lmed = statistics.median(left)
rmed = statistics.median(right)

if N % 2 == 0:
    print(int((rmed - lmed) * 2 + 1))
else:
    print(rmed - lmed + 1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline
n = int(rl())
a = []
b = []
for _ in range(n):
    aa, bb = map(int, rl().split())
    a.append(aa)
    b.append(bb)

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
a = heapsort(a)
b = heapsort(b)
if n&1:
    ans = b[n//2] - a[n//2] + 1
else:
    c = a[n//2] + a[n//2 - 1]
    d = b[n//2] + b[n//2 - 1]
    ans = (d/2 - c/2) / 0.5 + 1
print(int(ans))

Submission status: Accepted

Solution code:
TEST = False

if not TEST:
    N = int(input())
    AS = []
    BS = []
    for i in range(N):
        A, B = [int(x) for x in input().split()]
        AS.append(A)
        BS.append(B)


def getBound(AS, BS):
    """
    >>> getBound([0, 1], [1, 2])
    1 3 3
    >>> getBound([0, 0], [1, 2])
    1 3 3
    >>> getBound([0, 1, 2], [1, 2, 3])
    1 2 2
    >>> getBound([0, 1, 2], [1, 3, 3])
    1 3 3
    >>> getBound([0, 0, 1], [2, 3, 3])
    0 3 4
    """
    N = len(AS)
    AS2 = AS[:]
    AS2.sort()

    BS2 = BS[:]
    BS2.sort()
    if N % 2 == 0:
        lower = AS2[N // 2 - 1] + AS2[N // 2]
        upper = BS2[N // 2 - 1] + BS2[N // 2]
        result = upper - lower + 1
    else:
        lower = AS2[N // 2]
        upper = BS2[N // 2]
        result = upper - lower + 1
    if TEST:
        print(lower, upper, result)
    else:
        return result


def _test():
    import doctest
    doctest.testmod()


if TEST:
    _test()
else:
    print(getBound(AS, BS))

Submission status: Accepted

Solution code:

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A, B = [], []
    for _ in range(N):
        a, b = ZZ()
        A.append(a)
        B.append(b)
    A.sort()
    B.sort()
    midA = A[N//2] if N%2 == 1 else (A[N//2-1] + A[N//2])
    midB = B[N//2] if N%2 == 1 else (B[N//2-1] + B[N//2])
    print(midB-midA+1)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
#    li = []
    min_list = []
    max_list = []
    for _ in range(n):
        a, b = map(int, input().split(" "))
#        li.append([a, b])
        min_list.append(a)
        max_list.append(b)

    min_list.sort()
    max_list.sort()

    min_val2 = 1
    max_val2 = 1
    if n%2 == 0:
        cent1 = n//2-1
        cent2 = n//2
        min_val2 = min_list[cent1] + min_list[cent2]
        max_val2 = max_list[cent1] + max_list[cent2]
    else:
        cent = (n+1)//2-1
        min_val2 = min_list[cent]
        max_val2 = max_list[cent]

    ans = max_val2 - min_val2 + 1
    print(ans)

# else:
    # do nothing

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    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:
        start = A[((N + 1) // 2) - 1]
        last = B[((N + 1) // 2) - 1]
        print(last - start + 1)
    else:
        start = (A[(N // 2) - 1] + A[(N // 2 + 1) - 1]) / 2
        last = (B[(N // 2) - 1] + B[(N // 2 + 1) - 1]) / 2
        print(int((last - start) * 2 + 1))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

d = sorted(d)
u = sorted(u, reverse=True)
if n % 2 == 0:
    dl = (d[n//2] + d[n//2-1]) / 2
    ul = (u[n//2] + u[n//2-1]) / 2
    ans = int((ul-dl) / 0.5 + 1)
else:
    dl = d[n//2]
    ul = u[n//2]
    ans = ul-dl+1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

AB = [map(int, input().split()) for _ in range(N)]
A, B = map(list, zip(*AB))

listXmin = []
listXmax = []
maxXi = 0
minXi = 10 ** 10
for i in range(N):
    listXmin.append(A[i])
    listXmax.append(B[i])

listXmin.sort()
listXmax.sort()
if N % 2 == 0:
    centrali = int(N / 2) - 1
    centralinext = int(N / 2)
    print(((listXmax[centrali] + listXmax[centralinext]) - (listXmin[centrali] + listXmin[centralinext])) + 1)
else:
    centrali = int((N + 1) / 2) - 1
    print(listXmax[centrali] - listXmin[centrali] + 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= sorted(aa)[(n-1)//2:]
bb= sorted(bb,reverse=True)[(n-1)//2:]
if n%2==1:
  print(abs(bb[0]-aa[0])+1)
else:
  print((bb[0]+bb[1])-(aa[0]+aa[1])+1)

Submission status: Accepted

Solution code:
n = int(input())

rs = []
aes = []
bs = []

for _ in range(n):
  a, b = map(int, input().split())
  rs.append([a,b])
  aes.append(a)
  bs.append(b)


aes.sort()
bs.sort(reverse=True)

if n % 2 == 1:
  p = aes[(n - 1) // 2]
  q = bs[(n - 1) // 2]
  ans = q - p + 1
else:
  p1 = aes[n // 2 - 1]
  p2 = bs[n // 2]
  q1 = aes[n // 2]
  q2 = bs[n // 2 - 1]
  ans = (p2 - p1 + 1) + (q2- q1 + 1) - 1
 
# print(p1, p2, q1, q2)
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]", B: "List[int]"):
    A.sort()
    B.sort(reverse=True)
    if N % 2 == 0:
        Xa1 = A[N // 2 - 1]
        Xa2 = A[N // 2]
        Xb1 = B[N // 2 - 1]
        Xb2 = B[N // 2]
        print(Xb2 + Xb1 - (Xa2 + Xa1) + 1)
    else:
        Xa = A[(N + 1) // 2 - 1]
        Xb = B[(N + 1) // 2 - 1]
        print(Xb - Xa + 1)
        
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())
A = []
B = []
for n 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:
    b = B[N//2]+B[N//2-1]
    a = A[N//2]+A[N//2-1]
    print (b-a+1)

Submission status: Accepted

Solution code:
N=int(input())
ls=[list(map(int,input().split())) for i in range(N)]
ls_a=sorted([ls[i][0] for i in range(N)])
ls_b=sorted([ls[i][1] for i in range(N)])
ls_b.reverse()

if N%2==1:
  print(ls_b[(N-1)//2]-ls_a[(N-1)//2]+1)
else:
  p=(ls_a[N//2-1]+ls_a[N//2])/2
  q=(ls_b[N//2-1]+ls_b[N//2])/2
  print(int((q-p)*2+1))

Submission status: Accepted

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

a_list.sort()
b_list.sort()

if n % 2 == 1:
    mid = (n+1)//2-1
    res = b_list[mid] - a_list[mid] + 1
else:
    mid_f = n//2-1
    mid_s = n//2
    max_sum = b_list[mid_s] + b_list[mid_f]
    min_sum = a_list[mid_s] + a_list[mid_f]
    res = max_sum - min_sum + 1

print(res)

Submission status: Accepted

Solution code:
n = int(input())
num = []


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

a = []
b = []
for i in range(n):
    a.append(num[i][0])
    b.append(num[i][1])

a.sort()
b.sort()

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = []
    B = []
    for i in range(N):
        a, b = NMI()
        A.append(a)
        B.append(b)
    A.sort()
    B.sort()

    if N%2:
        l = A[(N+1)//2-1]
        r = B[(N+1)//2-1]
        print(r-l+1)
        exit()

    ll = A[N//2-1]
    lr = A[N//2]
    rl = B[N//2-1]
    rr = B[N//2]
    l = (ll+lr)/2
    r = (rl+rr)/2
    gap = r-l
    print(int(gap*2+1))



if __name__ == "__main__":
    main()

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%2==1:
    a_m = a[n//2]
    b_m = b[n//2]
    ans=max(b_m-a_m+1,0)
    print(ans)
else:
    a_m = (a[n//2]+a[n//2-1])
    b_m = (b[n//2]+b[n//2-1])
    ans = max(b_m-a_m+1,0)
    print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    L = [list(map(int,input().split())) for _ in range(N)]
    L = sorted(L)
    M = sorted(L,key=lambda x: x[1])
    if N%2 == 1:
        print(max(0,M[N//2][1]-L[N//2][0]+1))
    else:
        a = (L[N//2-1][0]+L[N//2][0])
        b = (M[N//2-1][1]+M[N//2][1])
        print(b-a+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    k = (n - 1) // 2
    ab = [[int(i) for i in read().split()] for _ in range(n)]
    a = sorted(a for a, _ in ab)
    b = sorted(b for _, b in ab)
    if n % 2:
        print(b[-1 - k] - a[k] + 1)
    else:
        i = a[k] + a[k + 1]
        j = b[-1 - k - 1] + b[-1 - k]
        print(j - i + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import statistics as s

n = int(input())

minn = []
maxx = []

for i in range(0,n):
    temp = [int(x) for x in input().split()]

    minn.append(temp[0])
    maxx.append(temp[1])

a = s.median(minn)
b = s.median(maxx)

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

Submission status: Accepted

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

def main():
    n = int(input())
    low = []
    high = []

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

    low.sort()
    high.sort()

    if n%2 == 1:
        l = low[n//2]
        h = high[n//2]
    else:
        l = low[n//2 - 1] + low[n//2]
        h = high[n//2 - 1] + high[n//2]

    ans = h - l + 1

    print(ans)

main()

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

Submission status: Accepted

Solution code:
n = int(input())
points = set()
A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    if n % 2 == 0:
        a *= 2
        b *= 2
    A.append(a)
    B.append(b)


A.sort()
B.sort()

if n % 2 == 0:
    src = (A[n // 2 - 1] + A[n // 2]) // 2
    dst = (B[n // 2 - 1] + B[n // 2]) // 2
else:
    src = A[n // 2]
    dst = B[n // 2]

print(dst - src + 1)

Submission status: Accepted

Solution code:
n = int(input())
a_list = []
b_list = []
c_list = []
for _ in range(n):
    a, b = map(int, input().split())
    c_list.append([a, b])
    a_list.append(a)
    b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 1:
    ans = b_list[n // 2] - a_list[n // 2] + 1
else:
    ans_first_max = b_list[(n // 2) - 1]
    ans_first_min = a_list[(n // 2) - 1]
    ans_second_max = b_list[(n // 2)]
    ans_second_min = a_list[(n // 2)]
    ans = (ans_second_max + ans_first_max) - ((ans_second_min + ans_first_min)) + 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
L=[list(map(int,input().split())) for i in range(n)]
minl=sorted([L[i][0] for i in range(n)])
maxl=sorted([L[i][1] for i in range(n)])
if n%2==1:
    mi=minl[n//2]
    ma=maxl[n//2]
    print(ma-mi+1)
else:
    mi=(minl[(n-1)//2]+minl[n//2])/2
    ma=(maxl[(n-1)//2]+maxl[n//2])/2
    print(int((ma-mi)//0.5+1))

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:
    M = B[N // 2]
    m = A[N // 2]
    print(M - m + 1)

else:
    M = (B[N // 2 - 1] + B[N // 2]) / 2
    m = (A[N // 2 - 1] + A[N // 2]) / 2
    print(int((M - m - 0.5) * 2 + 2))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

from decimal import Decimal
A = []
B = []
for _ in range(n):
    a, b = map(Decimal, input().split())
    A.append(a)
    B.append(b)



A = sorted(A)
B = sorted(B)



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



if n % 2 == 1:
    print(bm - am + 1)
else:
    print(int((bm - am) * 2 + 1))

Submission status: Accepted

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

if N%2==1:
  M=N//2
  C.sort(key=lambda x:x[0])
  p=C[M][0]
  C.sort(key=lambda x:x[1],reverse=True)
  q=C[M][1]
  print(q-p+1)
else:
  M=N//2
  C.sort(key=lambda x:x[0])
  p=C[M-1][0]
  C.sort(key=lambda x:x[1])
  q=C[M-1][1]
  C.sort(key=lambda x:x[0],reverse=True)
  r=C[M-1][0]
  C.sort(key=lambda x:x[1],reverse=True)
  s=C[M-1][1]
  #print(p,q,r,s)
  x=q-p+1
  y=s-r+1
  print(x+y-1)

Submission status: Accepted

Solution code:
import statistics

n=int(input())
a = [[int(i) for i in input().split()] for j in range(n)]
min=[i[0] for i in a]
max=[i[1] for i in a]
if n%2==0:
    print(int(statistics.median(max)*2-statistics.median(min)*2)+1)
else:
    print(int(statistics.median(max)-statistics.median(min))+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    X = []
    for i in range(N):
        A, B = map(int, input().split())
        X.append([A,B])
    d = defaultdict(list)
    X.sort()

    for i, x in enumerate(X):
        d[i+1].append(x[0])
    X.sort(key=lambda x: x[1])

    for i, x in enumerate(X):
        d[i+1].append(x[1])
    if N % 2 == 1:
        ans = d[(N+1)//2][1] - d[(N+1)//2][0] + 1
        print(ans)
    else:
        ans = (d[N//2][1] + d[N//2 + 1][1]) - (d[N//2][0] + d[N//2 + 1][0]) + 1
        print(ans)


    
    
    
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N)]

A = sorted([a for a,_ in AB])
B = sorted([b for _,b in AB])

if N % 2 == 1: # 奇数
    MIN = A[(N + 1) // 2 - 1]
    MAX = B[(N + 1) // 2 - 1]

else: # 偶数
    MIN = A[N // 2 - 1] + A[N // 2]
    MAX = B[N // 2 - 1] + B[N // 2]

print(MAX - MIN + 1)

Submission status: Accepted

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


n = int(input())

tank = []
dg = 10**10
mi = []
ma = []

for _ in range(n):
    a,b = map(int,input().split())
    tank.append(a*dg + b)
    mi.append(a)
    ma.append(b)

mi.sort()
ma.sort(reverse = True)

if n % 2 == 1:
    c = mi[n//2]
    d = ma[n//2]
    print(d-c+1)
else:

    c = (mi[(n//2) - 1] + mi[n//2])
    d = (ma[(n//2) - 1] + ma[n//2])

    print(d-c+1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = []
    T = []
    for _ in range(N):
        a,b = map(int, input().split())
        S.append(a)
        T.append(b)
    S.sort()
    T.sort(reverse=True)
    if N % 2 == 1:
        print(T[N//2] - S[N//2] + 1)
    else:
        x = (T[N//2-1] + T[N//2])/2
        y = (S[N//2-1] + S[N//2])/2
        print(int((x - y) * 2) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
AB = []
low = []
up = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append([A, B])
    low.append(A)
    up.append(B)
    
low = sorted(low)
up = sorted(up)
    
if N%2 == 1:
    m_up = up[N//2]
    m_low = low[N//2]
    ans = m_up-m_low+1
    print(ans)
else:
    m_up = up[N//2] + up[N//2-1]
    m_low = low[N//2-1] + low[N//2]
    ans = m_up-m_low+1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())

s=[]
e=[]
for i in range(n):
  a,b=map(int,input().split())
  s.append(a)
  e.append(b)

s=sorted(s)
e=sorted(e,reverse=True)

x=n//2
if n%2==1:
  ans=(e[x]-s[x]+1)

else:
  ts=(s[x]+s[x-1])/2
  te=(e[x]+e[x-1])/2
  ans=(te-ts)//0.5+1

print(int(ans))

Submission status: Accepted

Solution code:
'''     ##     ##  #######  # #  ######
        ##     ##  ##   ##  ###    ##
        ##     ##  ##    #  # #    ##
        #########  #######  # #    ##    '''

import sys
import math
# sys.setrecursionlimit(10**6)

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

def printspx(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")
def printchk(*args): return print(*args, end=" \ ")

MODPRIME = int(1e9+7); BABYMOD = 998244353;

if __name__ == "__main__":
    # sys.stdin = open("input.txt","r")  # <<<  ^o^  Comment this line  ^_^  >>>
    n = int(input())
    lia = []
    lib = []
    for i in range(n):
        a, b = get_ints()
        lia.append(a)
        lib.append(b)
    lia.sort()
    lib.sort()
    if n % 2 == 0:
        ind1 = n//2 - 1
        ind2 = n//2
        m1 = (lia[ind1] + lia[ind2]) / 2
        m2 = (lib[ind1] + lib[ind2]) / 2
        print(int((m2 - m1)*2 + 1))
    else:
        ind = ((n+1)//2) - 1
        m1 = lia[ind]
        m2 = lib[ind]
        print(m2-m1+1)
# #############################################################################
'''
THE LOGIC AND APPROACH IS BY ME @luctivud ( UDIT GUPTA )
SOME PARTS OF THE CODE HAS BEEN TAKEN FROM WEBSITES LIKE::
(I Own the code if no link is provided here or I may have missed mentioning it)
>>> DO NOT PLAGIARISE.
TESTCASES:
'''