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:
# E

N = int(input())

ab = []

for i in range(N):
  ab.append(tuple(map(int,input().split())))

ab.sort()
  
import statistics
import math

am = statistics.median([i[0] for i in ab])
bm = statistics.median([i[1] for i in ab])

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

Submission status: Accepted

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

if N % 2 == 0:
    min1 = A[N//2-1]
    min2 = A[N//2]
    max2 = B[-N//2]
    max1 = B[-N//2-1]
    # print(min1, min2, max1, max2)
    ans = ((max2 + max1) / 2 - (min2 + min1) / 2) * 2 + 1
else:
    mini = A[N//2]
    maxi = B[-N//2]
    # print(mini, maxi)
    ans = maxi - mini + 1
print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    ab = [list(map(int,input().split())) for i in range(n)]
    ab.sort(key=lambda x: x[1])
    ab2 = sorted(ab)
    if n%2 == 0:
        a = ab2[n//2-1][0]
        b = ab[n//2-1][1]
        c = ab2[n//2][0]
        d = ab[n//2][1]
        # print(a,b,c,d)
        print((b-a+1)+(d-c))
    else:
        a = ab2[n//2-1][0]
        b = ab[n//2-1][1]
        c = ab2[n//2][0]
        d = ab[n//2][1]
        e = ab2[n//2+1][0]
        f = ab[n//2+1][1]
        
        # l = c
        # r = d
        # print(ab)
        # print(a,b,c,d,e,f)
        # if l < b:
        #     l = b
        # if l > e:
        #     l = e
        # if r > e:
        #     r = e
        #     # print(r)
        # if r < b:
        #     r = b
        # # print(r,l)
        # # print(r-l+1)
        ll = [a,c,e]
        rl = [b,d,f]
        ll.sort()
        rl.sort()
        print(rl[1] - ll[1] +1 )
        # print(ab)
        # print(ab2)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

nums = [[0, 0] for _ in range(n)]

for i in range(n):
  nums[i][0], nums[i][1] = map(int, input().split())
  
if n % 2 == 0:
  # even
  nums.sort(key=lambda x: x[0])
  a = (nums[(n+1)//2 - 1][0] + nums[(n+1)//2][0])
  nums.sort(key=lambda x: x[1])
  b = (nums[(n+1)//2 - 1][1] + nums[(n+1)//2][1])
  print(b-a + 1)
  
else:
  # odd
  nums.sort(key=lambda x: x[0])
  a = nums[(n+1)//2 - 1][0]
  nums.sort(key=lambda x: x[1])
  b = nums[(n+1)//2 - 1][1]
  print(b-a + 1)

Submission status: Accepted

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

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 == 1:
    ans_mi = a[N//2]
    ans_ma = b[N//2]
    print(ans_ma-ans_mi+1)
else:
    ans_mi = (a[N//2]+a[N//2-1])/2
    ans_ma = (b[N//2]+b[N//2-1])/2
    ans=(ans_ma-ans_mi)//0.5+1
    print(int(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
  
def main():
    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:
        L = (A[N//2 - 1] + A[N//2])
        R = (B[N//2 - 1] + B[N//2])
        ans = (R - L + 1)
    else:
        L = A[N//2]
        R = B[N//2]
        ans = R - L + 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# print(ab)
alst=[0]*n
blst=[0]*n
for i in range(n):
    a,b=ab[i]
    alst[i]=a
    blst[i]=b
alst.sort()
blst.sort()
# print(alst)
# print(blst)
if n%2==0:
    # print((alst[n//2]+alst[n//2-1])/2)
    # print((blst[n//2]+blst[n//2-1])/2)
    print(int(((blst[n//2]+blst[n//2-1])/2-(alst[n//2]+alst[n//2-1])/2)*2+1))
else:
    # print(alst[n//2])
    # print(blst[n//2])
    print(blst[n//2]-alst[n//2]+1)

Submission status: Accepted

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

As.sort()
Bs.sort()
if N % 2 == 0:
    mins = (As[N//2] + As[N//2-1]) / 2.0
    maxs = (Bs[N//2] + Bs[N//2-1]) / 2.0
    print(int((maxs-mins)/0.5)+1)
else:
    mins,maxs = As[N//2], Bs[N//2]

    print(int(maxs-mins)+1)

Submission status: Accepted

Solution code:
import bisect

n = int(input())

l = []
r = []

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

l.sort()
r.sort(reverse=True)

if n%2 == 1:
    print(r[(n-1)//2]-l[(n-1)//2]+1)
else:
    l1, l2 = l[(n-2)//2], l[(n-2)//2+1]
    r1, r2 = r[(n-2)//2+1], r[(n-2)//2]
    d1, d2 = r1-l1+1, r2-l2+1
    d1, d2 = max(d1, d2), min(d1, d2)
    print(r2+r1-l1-l2+1)

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

N = int(input())
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))

A = []
B = []

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

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])+1)

Submission status: Accepted

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

A_sorted = sorted(A)
B_sorted = sorted(B)

if N % 2 != 0:
    n = N // 2
    a = A_sorted[n]
    b = B_sorted[-(n+1)]
    print(b-a+1)
else:
    n = N // 2
    a1 = A_sorted[n-1]
    a2 = A_sorted[n]
    b1 = B_sorted[-n]
    b2 = B_sorted[-n-1]
    a = (a1 + a2) / 2
    b = (b1 + b2) / 2
    print(int((b-a)*2 + 1))

Submission status: Accepted

Solution code:
min_li, max_li = [], []
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    min_li.append((a, b))
    max_li.append((a, b))
min_li.sort()
max_li.sort(key=lambda x: x[1], reverse=True)
if n % 2 == 1:
    mid = n // 2
    blue_min = min_li[mid][0]
    blue_max = min(min_li[mid:], key=lambda x: x[1])[1]
    red_max = max_li[mid][1]
    red_min = max(max_li[mid:])[0]
else:
    mid_1 = n // 2 - 1
    mid_2 = n // 2
    min_li_half = sorted(min_li[mid_1:], key=lambda x: x[1])
    blue_min = min_li[mid_1][0] + min_li[mid_2][0]
    blue_max = min_li_half[0][1] + min_li_half[1][1]
    max_li_half = sorted(max_li[mid_1:], reverse=True)
    red_max = max_li[mid_1][1] + max_li[mid_2][1]
    red_min = max_li_half[0][0] + max_li_half[1][0]

ans = red_max - blue_min + 1

print(ans)

Submission status: Accepted

Solution code:
import statistics

n = int(input())
alist = []
blist = []
for i in range(n):
    a,b = map(int,input().split())
    alist.append(a)
    blist.append(b)
minMed = statistics.median(alist)
maxMed = statistics.median(blist)

if n%2 == 1:
    print(maxMed-minMed+1)
else:
    if (minMed*2) % 2 == 0:
        if (maxMed*2) % 2== 0:
            diff = maxMed - minMed
            print(int(2*diff + 1))
        else:
            print(int((maxMed*2 - minMed*2) +1))
    else:
        if (maxMed*2)%2 == 0:
            print(int((maxMed*2 - minMed*2) +1))
        else:
            diff = 2*maxMed - 2*minMed
            print(int(diff+1))

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], B[i] = a, b
mx, mn = 0, 0
B.sort()
A.sort()
if N%2 == 0:
    mx = (B[N//2-1]+B[N//2+1-1])/2
    mn = (A[N//2-1]+A[N//2+1-1])/2
else:
    mx = B[(N+1)//2-1]
    mn = A[(N+1)//2-1]
#print(B, A)
#print(mx, mn)
if N%2 == 0:
    print(int(2*(mx-mn)+1))
else:
    print(mx-mn+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
n=int(input())
r=set([])
x=[[]]*n
for i in range(n):
  a,b=list(map(int,input().split()))
  x[i]=[a,b]
r0=statistics.median([x[z][0] for z in range(n)])
r1=statistics.median([x[z][1] for z in range(n)])
addnum = 1
if ((r0*2) % 2)>0 and ((r1*2) % 2)>0:
  mult=2
  addnum = 1
elif ((r0*2) % 2)>0:
  mult=2
  addnum = 0  
elif ((r1*2) % 2)>0:
  mult=2
  addnum = 0  
else:
  mult=1
  addnum = 1
#print(r0)
#print(r1)
if n%2 ==0:
  mult=2
else:
  mult=1
addnum=1
mult=int((r1-r0)*mult+addnum)
print(mult)
  #r=r|

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
AB = li2(N)
A = [0]*N
B = [0]*N
for i in range(N):
    A[i] = AB[i][0]
    B[i] = AB[i][1]

if N%2:
    num_a = sorted(A)[N//2]
    num_b = sorted(B)[N//2]
    print(num_b-num_a+1)
else:
    A_ = sorted(A)
    B_ = sorted(B)
    min_a = A_[N//2-1]
    max_a = A_[N//2]
    min_b = B_[N//2-1]
    max_b = B_[N//2]
    #print(max(max_b, )-min(min_a, min_b)+1)
    print(max_b+min_b-(max_a+min_a)+1)

Submission status: Accepted

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

a = sorted(l, key=lambda x:x[0])
b = sorted(l, key=lambda x:x[1])

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

Submission status: Accepted

Solution code:
N = int(input())
AB = [tuple(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 == 1:
    id = (N+1)//2
    print(B[-id] - A[id-1] + 1)
else:
    id = N // 2
    ans = (B[-id-1]-A[id])*2 + 1
    ans += B[-id] - B[-id-1]

    ans += A[id] - A[id-1]

    print(ans)

Submission status: Accepted

Solution code:
N=int(input())

alist,blist=[],[]
for _ in range(N):
  a,b=map(int,input().split())
  alist.append(a)
  blist.append(b)
alist.sort()
blist.sort()
#print(ablist,alist,blist)

if N%2==1:
  left=alist[N//2]
  right=blist[-N//2]
  #print(left,right)
  print(right-left+1)
else:
  left1=alist[N//2-1]
  left2=alist[N//2]
  right1=blist[-N//2-1]
  right2=blist[-N//2]
  #print(left1,right1,left2,right2)
  print(right1+right2-left1-left2+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis1=[];lis2=[]
for i in range(n):
    a,b=MI()
    lis1.append(a)
    lis2.append(b)
lis1.sort()
lis2.sort()
if n%2==1:
    ans=max(0,lis2[(n-1)//2]-lis1[(n-1)//2]+1)
else:
    sup1=lis2[n//2-1]
    sup2=lis2[n//2]
    low1=lis1[n//2-1]
    low2=lis1[n//2]
    ans=(sup1+sup2-low1-low2+1)
    ans=max(ans,0)
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:
    a = A[(N-1)//2]
    b = B[(N-1)//2]
    print(b - a + 1)
else:
    a = (A[N//2-1] + A[N//2]) / 2
    b = (B[N//2-1] + B[N//2]) / 2
    print(int((b-a)*2+1))

Submission status: Accepted

Solution code:
n=int(input())
m,M=[],[]
for i in range(n):
  a,b=map(int,input().split())
  m+=[a]
  M+=[b]
m.sort()
M.sort()
d=n//2
print(M[d]-m[d]+1+(M[d-1]+-m[d-1])*(1-n%2))

Submission status: Accepted

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

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

A = [C[i][0] for i in range(n)]
B = [C[i][1] for i in range(n)]

ans = 0
if n%2==1:
    ans = statistics.median(B)-statistics.median(A)+1
    print(ans)
else:
    a = statistics.median(A)
    b = statistics.median(B)
    eps = 10**-3
    print(int(b*2+eps)-int(a*2+eps)+1)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = [0]*(n+1)
b = [0]*(n+1)
for i in range(1,n+1):
    aa, bb = MAP()
    a[i] = aa
    b[i] = bb

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

print(res)

Submission status: Accepted

Solution code:
N = int(input())

A = []
B = []
for _ in range(N):
    a, b = [int(_) for _ in 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:
    sa, ea = A[N//2 - 1], B[N//2 - 1]
    sb, eb = A[N//2], B[N//2]
    print(eb+ea - (sa+sb) + 1)

Submission status: Accepted

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

# process
A.sort()
B.sort()

if N%2 == 1:
    m = (N+1)//2-1
    ans = B[m] - A[m] + 1
else:
    m1 = N//2-1
    m2 = m1+1
    ans = int(((B[m1]+B[m2])/2-(A[m1]+A[m2])/2)*2)+1
    
# output
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a =[]
b = []
for i in range(n):
    l= list(map(int,input().split()))
    a += [l[0]]
    b += [l[1]]

a = sorted(a)
b = sorted(b, reverse=True)

if n % 2 == 0:
    k = n//2 -1
    
    aa = (a[k] + a[k +1]) /2
    bb= (b[k] + b[k + 1]) /2
    
    r = (bb-aa) * 2 + 1
    
else:
    k = n//2
    
    aa = a[k]
    bb= b[k]
    
    r = (bb-aa)  + 1
    

print(int(r))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
min_list=[0]*n
max_list=[0]*n
result = 0

for i in range(n):
    a, b = map(int, input().split())
    min_list[i] = a
    max_list[i] = b

min_list.sort()
max_list.sort()

# print(min_list)
# print(max_list)
if n%2 == 0:
    center_idx = n // 2
#    print(center_idx)
    result = max_list[center_idx] + max_list[center_idx-1] - min_list[center_idx] - min_list[center_idx-1] + 1
else:
    center_idx = n // 2
#    print(center_idx)
    result = max_list[center_idx] - min_list[center_idx] + 1
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def main():
    n = int(input().strip())

    diff_a = defaultdict(int)
    diff_b = defaultdict(int)
    for _ in range(n):
        a, b = map(int, input().split())
        diff_a[a] += 1
        diff_b[b] += 1

    cur = 0
    for i in sorted(diff_a):
        cur += diff_a[i]
        if cur >= n // 2 + 1:
            b1 = i
            break
    cur = 0
    for i in sorted(diff_b, reverse=True):
        cur += diff_b[i]
        if cur >= n // 2 + 1:
            e1 = i
            break

    if n % 2 == 1:
        print(e1 - b1 + 1)
        return

    cur = 0
    for i in sorted(diff_a):
        cur += diff_a[i]
        if cur >= n // 2:
            b2 = i
            break
    cur = 0
    for i in sorted(diff_b, reverse=True):
        cur += diff_b[i]
        if cur >= n // 2:
            e2 = i
            break
    ans = e2 + e1 - (b1 + b2) + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [[0 for _ in range(2)] for _ in range(N)]
for i in range(N):
    A[i] = list(map(int,input().split()))
if len(A) % 2 == 1:
    max_A = [A[i][1] for i in range(N)]
    min_A = [A[i][0] for i in range(N)]
    max_A.sort()
    min_A.sort()
    max_ = max_A[(len(A))//2]
    min_ = min_A[(len(A))//2]
    print(max_ - min_ + 1)

else:
    max_A = [A[i][1] for i in range(N)]
    min_A = [A[i][0] for i in range(N)]
    max_A.sort()
    min_A.sort()
    max_ = max_A[(len(A))//2]
    max_c = max_A[(len(A))//2 - 1]
    min_ = min_A[(len(A))//2]
    min_c = min_A[(len(A))//2 - 1]
    aa = (max_ + max_c) / 2.0
    bb = (min_ + min_c) / 2.0
    print(int(2 * (aa-bb)) + 1)

Submission status: Accepted

Solution code:
n=int(input())
nlista=[]
nlistb=[]
for i in range(n):
    a,b=map(int,input().split())
    nlista.append(a)
    nlistb.append(b)
#print(nlista,nlistb)
nlista.sort()
nlistb.sort()
#print(nlista,nlistb)

ansl=0
ansh=0
n2=n//2
#print(n2)
if n%2:
    ansl=nlista[n2]
    ansh=nlistb[n2]
else:
    ansl=nlista[n2-1]+nlista[n2]
    ansh = nlistb[n2-1] + nlistb[n2]
print(ansh-ansl+1)

Submission status: Accepted

Solution code:
import statistics
def main():
    N = int(input())
    A = []
    B = []
    for i in range(N):
        a, b = [int(_n) for _n in input().split()]
        A.append(a)
        B.append(b)
    a = statistics.median(A)
    b = statistics.median(B)
    # print(a,b)
    if N % 2 == 0:
        print(int(2 * (b-a))+1)
    else:
        print(int(b-a)+1)


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)
from statistics import median
Am = median(A)
Bm = median(B)
if N%2==1:
    ans = Bm-Am+1
    print(ans)
else:
    ans = int((Bm-Am)*2+1)
    print(ans)

Submission status: Accepted

Solution code:
N, *AB = map(int, open(0).read().split())

A = sorted(zip(*[iter(AB)] * 2), key=lambda t: t[0])
B = sorted(zip(*[iter(AB)] * 2), key=lambda t: t[1])

if N % 2 == 1:
    L = A[N // 2][0]
    R = B[N // 2][1]
else:
    L = A[N // 2 - 1][0] + A[N // 2][0]
    R = B[N // 2 - 1][1] + B[N // 2][1]

print(R - L + 1)

Submission status: Accepted

Solution code:
# 多次元リストのsortに使える
from operator import itemgetter

def solve(n,a,b):
    if n % 2 == 0:
        s = n // 2
        t = s - 1
        k1 = [0,0]
        k2 = [0,0]


        ast = sorted(a)
        k1[0] = ast[t]
        k2[0] = ast[s]

        bst = sorted(b)
        k1[1] = bst[t]
        k2[1] = bst[s]

        k = [(k1[0]+k2[0])/2,(k1[1]+k2[1])/2]
        return int(k[1]*2-k[0]*2+1)
    else:
        s = n // 2
        k = [0,0]
        ast = sorted(a)
        k[0] = ast[s]
        bst = sorted(b)
        k[1] = bst[s]

        return int(k[1]-k[0]+1)

if __name__ == '__main__':
    n = int(input())
    a = []
    b = []
    for i in range(n):
        ai,bi = map(int,input().split())
        a.append(ai)
        b.append(bi)
    print(solve(n,a,b))

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:
    index = int((N-1)/2)
    minX = A[index]
    maxX = B[index]
    ans = maxX - minX + 1
else:
    index = int(N/2)
    minX1 = A[index-1]
    minX2 = A[index]
    maxX1 = B[index-1]
    maxX2 = B[index]
    minX = minX1 + minX2
    maxX = maxX1 + maxX2
    ans = maxX - minX + 1

print(ans)

Submission status: Accepted

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


sA = sorted(A)
sB = sorted(B, reverse=True)



m = N//2

if N%2 == 1:
    minMid = sA[m]
    maxMid = sB[m]

    print(maxMid-minMid+1)
    exit()
else:
    m = m-1
    minMidL = sA[m]
    maxMidL = sB[m+1]

    minMidH = sA[m+1]
    maxMidH = sB[m]
    # print(minMidL, maxMidL)
    # print(minMidH, maxMidH)
    # print("=======")
    ans = set()
    aa = minMidL + minMidH
    bb = maxMidL + maxMidH
    # print(aa, bb)
    print(bb-aa + 1)
    # for i in range(minMidL, maxMidL+1):
    #     for j in range(max(i, minMidH), maxMidH+1):
            
    #         ans.add(i+j)
    # print(len(ans))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = np.array(AB)

# 取りうる最小の中央値と最大の中央値を計算
m = np.median(AB[:, 0])
M = np.median(AB[:, 1])

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

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
import bisect
setrecursionlimit(10 ** 7)

n = int(input())
li = []
lin = []

for _ in range(n):
    a,b = map(int,stdin.readline().rstrip().split())
    li.append([a,b])
    lin.append([b,a])

li.sort()
lin.sort()

if n%2 == 1:
    print(lin[n//2][0]-li[n//2][0]+1)
else:
    print((lin[n//2][0]+lin[(n-1)//2][0])-(li[n//2][0]+li[(n-1)//2][0])+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
AB = [tuple(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 = [(AB[i][0], i) for i in range(n)]
# B = [(AB[i][1], i) for i in range(n)]

A.sort()
B.sort()

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


if n % 2 == 0:
    # x = abs(A[n // 2 - 1] + B[n // 2])
    # y = abs(A[n // 2] + B[n // 2 - 1])
    # print(x, y)
    # print(abs(x - y) + 1)

    # print(x, y)
    a = A[n // 2] + A[n // 2 - 1]
    b = B[n // 2] + B[n // 2 - 1]
    print(b - a + 1)
    # print(a, b)
    # print(B[n // 2] - A[n // 2 - 1] + 1)

Submission status: Accepted

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

if n % 2 == 1:
    print(abs(b[n//2] - a[n//2]) + 1)
else:
    t = [a[n // 2], a[n // 2 - 1], b[n // 2], b[n // 2 - 1]]
    print(int(abs((t[0] + t[1]) / 2 - (t[2] + t[3]) / 2) / 0.5) + 1)

Submission status: Accepted

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


def read_ints():
    return map(int, input().split(' '))


n = read_int()
a = []
b = []
for i in range(n):
    ai, bi = read_ints()
    a.append(ai)
    b.append(bi)
a.sort()
b.sort()
if n % 2 == 0:
    ma = a[n // 2 - 1] + a[n // 2]
    mb = b[n // 2 - 1] + b[n // 2]
    print(mb - ma + 1)
else:
    ma = a[n // 2]
    mb = b[n // 2]
    print(mb - ma + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from math import gcd, ceil
from collections import deque
# queueとして使う場合 push, popleftを使う
from bisect import bisect_left, bisect_right
# bisect_left: 配列の順序関係が崩れない条件で挿入することができる一番左の点
# bisect_right: 配列の順序関係が崩れない条件で挿入することができる一番右の点
# A = [1, 1, 1, 2, 2, 2, 4]
# print(bisect_left(A, 2))  # 3
# print(bisect_right(A, 2))  # 6
# print(bisect_left(A, 3))  # 6
# print(bisect_right(A, 3))  # 6


def main():
    N = int(input())
    Bs = []
    As = []
    for i in range(N):
        a, b = map(int, input().split())
        As.append(a)
        Bs.append(b)
    min_med = np.median(As)
    max_med = np.median(Bs)
    if N % 2 == 0:
        print(int(2 * (max_med - min_med) + 1))
    else:
        print(int((max_med - min_med) + 1))
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import copy
from collections import deque
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()

li = []
for _ in range(n):
    li.append(na())

li.sort()

def solve_odd():
    mid = int((n-1)/2)
    li.sort()
    left = li[mid][0]
    li.sort(key=lambda x: x[1])
    right = li[mid][1]
    print(right-left+1)

def solve_even():
    mid = int(n/2)
    li.sort()
    left1 = li[mid-1][0]
    left2 = li[mid][0]
    li.sort(key=lambda x: x[1])
    right1 = li[mid-1][1]
    right2 = li[mid][1]
    st = (left1+left2)/2
    en = (right1+right2)/2
    print(int((en-st)*2+1))


if n%2:
    solve_odd()
else:
    solve_even()

Submission status: Accepted

Solution code:
n = int(input())
a = [-1]
b = [-1]
for _ in range(n):
	ai,bi = map(int,input().split())
	a.append(ai)
	b.append(bi)
a = sorted(a)
b = sorted(b)
count = 0
if n%2 == 1:
	count = b[(n+1)//2] - a[(n+1)//2] + 1
else:
	a1 = a[n//2]
	b1 = b[n//2]
	a2 = a[n//2+1]
	b2 = b[n//2+1]
	count += 2*(b1-a2)+1
	count += (a2-a1)
	count += (b2-b1)
print(count)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N = int(input())
    An = [0] * N
    Bn = [0] * N
    for n in range(N):
        An[n], Bn[n] = [int(x) for x in input().strip().split()]
    An.sort()
    Bn.sort(reverse=True)
    if N % 2:
        A = An[(N+1)//2-1]
        B = Bn[(N+1)//2-1]
        print(B - A + 1)
    else:
        Amin = An[N//2-1]
        Amax = Bn[N//2]
        Bmax = Bn[N//2-1]
        Bmin = An[N//2]
        # print(Amin, Amax, Bmin, Bmax)
        print(int(((Bmax+Amax)/2-(Bmin+Amin)/2)//0.5+1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
#from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
a, b = [list(i) for i in zip(*ab)]
a.sort()
b.sort()
if n%2==1:
    ma=a[(n-1)//2]
    mb=b[(n-1)//2]
    print(mb-ma+1)
else:
    ma=a[n//2]+a[n//2-1]
    mb=b[n//2]+b[n//2-1]
    print(mb-ma+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)

medA = statistics.median(A)
medB = statistics.median(B)

if N % 2 == 1:
    print(medB - medA+1)
else:
    print(int((medB - medA)*2) + 1)

Submission status: Accepted

Solution code:
def main():
    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:
        a_t=(A[N//2]+A[N//2-1])/2
        b_t=(B[N//2]+B[N//2-1])/2
        print(int((b_t-a_t)//0.5+1))
    else:
        a_t=A[N//2]
        b_t=B[N//2]
        print(int((b_t-a_t)//1+1))
main()

Submission status: Accepted

Solution code:
N = int(input())
A = dict()
B = dict()
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A_sort = sorted(A.items(), key=lambda x:x[1])
B_sort = sorted(B.items(), key=lambda x:x[1])

if N % 2 == 1:
    print(B_sort[(N+1)//2-1][1]-A_sort[(N+1)//2-1][1]+1)
else:
    B_min = B_sort[N//2-1][1]
    A_min = A_sort[N//2-1][1]
    A_max = A_sort[N//2][1]
    B_max = B_sort[N//2][1]
    print(-A_max+B_max-A_min+B_min+1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    AB = [[int(e) for e in input().split()] for i in range(n)]

    Ma = sorted([ab[0] for ab in AB])
    Mb = sorted([ab[1] for ab in AB])
    if n % 2 == 1:
        mi = Ma[((n + 1) // 2) - 1]
        ma = Mb[((n + 1) // 2) - 1]
        print(ma - mi + 1)

    else:
        mi = (Ma[n // 2 - 1] + Ma[n // 2])
        ma = (Mb[n // 2 - 1] + Mb[n // 2])
        print(ma - mi + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import copy

n = int(input())
ab = sorted([list(map(int, input().split())) for i in range(n)])
abr = copy.copy(ab)
abr.sort(key=itemgetter(1))
if n % 2:
    a1,b1 = ab[n//2]
    a2,b2 = abr[n//2]
    ans = b2 - a1 + 1
else:
    a1,b1 = ab[n//2-1]
    a2,b2 = abr[n//2-1]
    a3,b3 = ab[n//2]
    a4,b4 = abr[n//2]
    ans = b4 - a3 + b2 - a1 + 1
print(ans)

Submission status: Accepted

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

    lowerlist = []
    upperlist = []

    for ab in AB:
        lowerlist.append(ab[0])
        upperlist.append(ab[1])

    lowerlist.sort()
    upperlist.sort(reverse=True)

    if N % 2 == 0:
        # すべて最低値を選んだときの中央値を求める
        lowermid = (lowerlist[N//2-1] + lowerlist[N//2]) / 2
        # すべて最高値を選んだときの中央値を求める
        uppermid = (upperlist[N//2-1] + upperlist[N//2]) / 2
        print(int((uppermid - lowermid) * 2) + 1)
    else:
        # すべて最低値を選んだときの中央値を求める
        lowermid = lowerlist[N//2]
        uppermid = upperlist[N//2]
        print(uppermid-lowermid+1)


if __name__ == "__main__":
    main()

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 == 0:
  print((max[n//2] + max[n//2 - 1]) -(min[n//2] + min[n//2 - 1])+ 1)
else:
  print(max[n//2]-min[n//2]+1)