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: Wrong Answer

Solution code:
def main():
    n = int(input())
    t = [[int(t)for t in input().split()]for _ in [0]*n]

    t_1 = sorted(t,key=lambda a: a[0])
    t_2 = sorted(t,key=lambda b:b[1],reverse=True)

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

        ans = a[1]-a[0]+b[1]-b[0] + 1
        print(ans)







if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

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:
    saisho = A[(n - 1) // 2]
    saidai = B[(n - 1) // 2]
    print(saidai - saisho + 1)
else:
    saisho1 = A[n // 2 - 1]
    saisho2 = A[n // 2]
    saidai1 = B[n // 2 - 1]
    saidai2 = B[n // 2]
    saidai = saidai2 + saisho2
    saisho = saidai1 + saisho1
    delta = saidai - saisho
    print(delta + 1)

Submission status: Wrong Answer

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:
    print(B[n % 2] - A[n // 2 - 1] + 1)

Submission status: Wrong Answer

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

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

for i in range(len(C)):
    for j in range(2):
        C[i][j] *= 2
# print(C)

l = 0
r = 10**10
m = (l+r)//2
while r-l > 1:
    c = 0
    d = 0
    for i in range(n):
        if C[i][1] < m:
            c += 1
        if C[i][1] > m:
            d += 1
    if c-d <= 0 or c-d < (n-c-d+1)//2:
        l = m
    else:
        r = m
    # print(l,r,m,c,d)
    m = (l+r)//2
# print(l)
aa = l
# print("aa",aa)

l = 0
r = 10**10
m = (l+r)//2
while r-l > 1:
    c = 0
    d = 0
    for i in range(n):
        if C[i][0] > m:
            c += 1
        if C[i][0] < m:
            d += 1
    if c-d <= 0 or c-d < (n-c-d+1)//2:
        r = m
    else:
        l = m
    # print(l,r,m,c,d)
    m = (l+r)//2
# print(r)
bb = r
# print("bb",bb)
ans = aa-bb+1
# print(ans)
if n%2 == 1:
    cc = (bb-1) // 2
    dd = aa // 2
    ans = dd - cc
    # print(dd,cc)
else:
    ans = aa - bb + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[]
A=[]
B=[]
for _ in range(n):
    a,b = map(int,input().split())
    AB.append((a,b))
    A.append(a)
    B.append(b)
#AB = sorted(AB,key=lambda x: x[1])
med = n//2
if n%2 != 0:
    print(B[n//2]-A[n//2]+1)
else:
    p = A[n//2] + A[n//2-1]
    q = B[n//2] + B[n//2-1]
    print(q-p+1)

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


class Compress:
    def __init__(self, ls):
        # 座標圧縮クラス(仮) #どうしたら使いやすくなるのか知らんけど
        self.i_to_orig = sorted(set(ls))
        self.orig_to_i = {}
        for i, zahyou in enumerate(self.i_to_orig):
            self.orig_to_i[zahyou] = i
        self.len = len(self.i_to_orig)

    def __len__(self):
        return len(self.i_to_orig)


N = read_a_int()
A, B = read_col(N)
A.sort()
B.sort()
if N & 1:
    print(B[N // 2] - A[N // 2] + 1)
else:
    l = (B[N // 2 - 1] + A[N // 2 - 1])
    r = (B[N // 2] + A[N // 2])
    print(r - l + 1)


# 偶数奇数でちょっとわけて考えよう
# Nが奇数なら→X[N//2]の候補の数

# 2つの領域の重なり方は3種類
# 1. 重なっていない
# 2. 一部重なっている
# 3. 完全に内包関係にある(ちょうどの場合も含む)

# 座標圧縮と前後ろから累積和で行けない？
# 一番lをXにしたときと一番rをXにしたとき,中央値の始まる端と終わる端がわかればよい

# 奇数の場合は

Submission status: Wrong Answer

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd,trunc
# n=int(input())
# l=list(map(int,input().split()))
# ans=1
# z=pow(10,18)
# for i in l:
# 	ans=ans*i
# 	if ans>z:
# 		ans=-1
# 		break
# if 0 in ans:
# 	print(0)
# else:
# 	print(ans)
# a,b=map(float,input().split())
# print(trunc(a*b))
n=int(input())
if n%2!=0:
	z=(n+1)//2
	for i in range(n):
		a,b=map(int,input().split())
		if z==i+1:
			print(b-a+1)
else:
	x=n//2
	y=n//2+1
	l=[]
	for i in range(n):
		a,b=map(int,input().split())
		if x==i+1:
			l.append([a,b])
		elif y==i+1:
			l.append([a,b])
	a=l[0][0]+l[1][0]
	b=l[1][1]+l[1][1]
	ans=b-a+1
	if b//2<a:
		pass
	else:
		c=b//2
		ans=ans-(c-a+1)
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n=int(input())
    s = [tuple(map(int, input().split())) for i in range(n)]
    a = sorted(i[0] for i in s)
    b = sorted(i[1] for i in s)
    lft = a[n//2] + a[-(n//2)-1]
    rgt = b[n//2] + b[-(n//2)-1]
    print((rgt - lft) // 2 * (2 if len(s) % 2 == 0 else 1) + 1)
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

left = AB[:]
right = AB[:]

left.sort()
right.sort(key = lambda x: x[1])
#print(left, right)

if N % 2:
    index = N // 2
    answer = right[index][1] - left[index][0] + 1
else:
    index1, index2 = N // 2 - 1, N // 2
    answer = right[index2][1] + right[index2][1] - (left[index2][0] + left[index2][0]) + 1
print(answer)

Submission status: Wrong Answer

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.sort()
b.sort()
if n&1:
    print(b[n//2]-a[n//2]+1)
else:
    print(1+(b[(n-1)//2]-a[n//2]+1)*2)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline
 
N=int(readline())
A = [None] * N
B = [None] * N
for i in range(N):
  A[i],B[i] = map(int,readline().split())

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

if N % 2 == 1:
  minval = A[N // 2]
  maxval = B[N // 2]
  print(max(maxval - minval + 1,0))
else:
  minval = A[(N - 1) // 2]
  maxval = B[(N) // 2]
  ran = maxval - minval + 1
  print((ran * (ran - 1)) // 2)

Submission status: Wrong Answer

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)

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

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

print(ans)

Submission status: Wrong Answer

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:
    print(B[n % 2 + 1] - A[n % 2] + 1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)
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:
    tmp = [a[n//2-1], a[n//2], b[n//2-1], b[n//2]]
    tmp.sort()
    print((tmp[1] + tmp[3]) - (tmp[0] + tmp[2]) + 1)
else:
    mid_l = a[n//2]
    mid_r = b[n//2]
    print(mid_r - mid_l + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
B = []

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
ABs_desc = deepcopy(ABs)
ABs.sort() #Aでソート
ABs_desc.sort(reverse=True)
if N%2:
    A1,B1 = ABs[N//2]
    A2,B2 = ABs_desc[N//2]
    if B1 < A2:
        print(B1-A1+1 + B2-A2+1)
    else:
        print(B2-A1+1)
else:
    A1,B1 = ABs[(N-1)//2]
    A2,B2 = ABs_desc[(N-1)//2]
    print(B1+B2-A1-A2+1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=sorted([list(map(int,input().split())) for i in range(n)])
b=sorted(a,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][1]+b[n//2][1])-(a[n//2-1][0]-a[n//2][0]))//2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A, B = [], []
for i in range(N):
    tm, p = map(int, input().split())
    A.append(tm), B.append(p)
A.sort(), B.sort()

a = A[N // 2] * 2 if N % 2 == 1 else A[N // 2 - 1] + A[N // 2]
b = B[N // 2] * 2 if N % 2 == 1 else B[N // 2 - 1] + B[N // 2]
print(b - a + 1 if N % 2 == 1 else b - a + 1)

Submission status: Wrong Answer

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:
  print(B[(n-1)//2] - A[(n-1)//2] + 1)
else:
  M = ( B[n//2 - 1] + B[n//2] ) / 2
  m = ( A[n//2 - 1] + A[n//2] ) / 2
  ans = int(M) - int(m)+1
  if M > int(M) and M!=m:
    ans +=1
#  print(m,M)
  print(ans)

Submission status: Wrong Answer

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


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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:
    ma = A[N//2]
    mb = B[N//2]
    print(mb-ma+1)
else:
    m = N//2
    ma = (A[m-1]+A[m])/2
    mb = (B[m-1]+B[m])/2
    mad = (A[m-1]+A[m])//2
    mau = (A[m-1]+A[m]+1)//2
    mbd = (B[m-1]+B[m])//2
    mbu = (B[m-1]+B[m]+1)//2
    
    if str(ma)[-1]=='5' and str(mb)[-1]=='5':
        print(mbu-mad+1)
    elif str(ma)[-1]=='5':
        print(mbd-mad+1)
    elif str(mb)[-1]=='5':
        print(mbu-mad+1)
    else:
        print(mbd-mad+1)

Submission status: Wrong Answer

Solution code:

N = int(input())
ans = []
pts = []
for i in range(N):
    x1, x2 = map(int, input().split())
    pts.append(x1)
    pts.append(x2)
pts = sorted(pts)

l = N // 2

if N % 2 == 0:
    L = (pts[l-1] + pts[l]) / 2
    R = (pts[-l] + pts[-l-1]) / 2
    ans = int((R-L)/(0.5)) + 1
else:
    ans = pts[-1-l] - pts[l] + 1
print(ans)

Submission status: Wrong Answer

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

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


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


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

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

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

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

Submission status: Wrong Answer

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

med = [i+j/2 for i in nums[:][0] for j in nums[:][1]]
print(len(set(med)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=sorted([list(map(int,input().split())) for i in range(n)])
b=sorted(a,key=lambda x:x[1])
if n%2==1:
    print(b[n//2][1]-a[n//2][0]+1)
else:
    print(int((b[n//2-1][1]+b[n//2][1])/2-(a[n//2-1][0]-a[n//2][0])/2))

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    ab = []
    odd = False
    if N % 2 == 1:
        odd = True
    for i in range(N):
        ab.append(LI())

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

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


main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(N, ABs):
    # print(N, ", ", ABs)
    starts = []
    ends = []
    for a, b in ABs:
        starts.append(a)
        ends.append(b)
    starts.sort()
    ends.sort()

    if N % 2 == 1:
        k = (N - 1) // 2
        left = starts[k]
        right = ends[-(k + 1)]
        return right - left + 1
    else:
        k = (N - 2) // 2
        left = starts[k]
        right = ends[-(k + 1)]
        d = (right - left - 1)
        e = (right - left)
        return d + e


# assert (solve(3, [(100, 100), (10, 10000), (1, 1000000000)]) == 9991)
# assert (solve(2, [(1, 2), (2, 3)]) == 3)

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


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


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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=sorted([list(map(int,input().split())) for i in range(n)])
b=sorted(a,key=lambda x:x[1])
if n%2==1:
    print(b[n//2][1]-a[n//2][0]+1)
else:
    print(math.ceil((b[n//2-1][1]+b[n//2][1])/2-(a[n//2-1][0]-a[n//2][0])/2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


l = 0
r = 10**9+1
while r - l > 1:
    m = l + (r-l)//2
    count = 0
    for i in range(n):
        if num[i][0] <= m:
            count += 1

    if count >= (n+1)//2:
        r = m
    else:
        l = m

left = r


l = 0
r = 10**9+1
while r - l > 1:
    m = l + (r-l)//2
    count = 0
    for i in range(n):
        if m <= num[i][1]:
            count += 1

    if count >= (n+1)//2:
        l = m
    else:
        r = m

right = l

if n % 2 == 0:
    print((right - left)*2 - 1)
else:
    print(right-left+1)

Submission status: Wrong Answer

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


mini=A[(N-1)//2]
maxi=B[(N-1)//2]
if N//2==0:
  print((maxi-mini)*2+1)
else:
  print(maxi-mini+1)

Submission status: Wrong Answer

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

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


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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
import bisect


def read():
    N = int(input().strip())
    AB = []
    for i in range(N):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, AB


def solve(N, AB, MOD=1000000007):
    A = list(sorted([a for a, b in AB]))
    B = list(sorted([b for a, b in AB]))
    if N % 2 == 1:
        m = N // 2
        low = A[m]
        high = B[m]
        return high - low + 1
    else:
        m = N // 2
        low = (A[m-1] + A[m]) // 2
        high = (B[m-1] + B[m]) // 2
        return (high - low) * 2 + 1
    return -1


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# max(A) <= X <= min(B) のXはすべて中央値可能
# 例: A = 1, 3, 6
# 1 3 6
# 1 4 6
# 1 5 6
# min(A) ~ max(A) の場合、
# Aをソートして中央値になる数 Y <= max(A) までが数？
# B も同様に B <= max(B)

import math

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

A.sort()
B.sort()

midA = A[(N+1)//2 - 1] if N % 2 == 1 else (A[N//2 - 1] + A[N//2])/2
midB = B[(N+1)//2 - 1] if N % 2 == 1 else (B[N//2 - 1] + B[N//2])/2

ans = min(B) - max(A) + 1
if isinstance(midA, float):
    if not midA.is_integer():
        midA = math.ceil(midA)
        ans += 1
if isinstance(midB, float):
    if not midB.is_integer():
        midB = math.floor(midB)
        ans += 1


if midA < max(A):
    ans += max(A) - midA
if midB > min(B):
    ans += midB - min(B)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ABs = list(tuple(map(int, input().split())) for _ in range(N))
ABs_sortby_A = sorted(ABs, key=lambda x: x[0])

a, b = ABs_sortby_A[N // 2]

print(b - a + 1)

Submission status: Wrong Answer

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:
  print(B[(n-1)//2] - A[(n-1)//2] + 1)
else:
  M = ( B[n//2 - 1] + B[n//2] ) / 2
  m = ( A[n//2 - 1] + A[n//2] ) / 2
  ans = int(M) - int(m)+1
  if M > int(M):
    ans +=1
  print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
ab2 = copy.deepcopy(ab)
ab = sorted(ab, key=lambda x:x[0])
ab2 = sorted(ab2, key=lambda x:x[1])
if n % 2 == 1:
    m = ab[n//2][0]
    M = ab2[n//2][1]
    print(max(0,M-m+1))
else:
    m = (ab[n//2][0]+ab[n//2-1][0])/2
    M = (ab[n//2][1]+ab[n//2-1][1])/2
    print(m,M)
    print(int((M-m)*2+1))

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _i in range(n)]
x, y = [], []
for i, j in ab:
    x.append(i)
    y.append(j)
x.sort()
y.sort(reverse=True)
if n%2==1:
    p = (n+1)//2 -1
    print(y[p]-x[p]+1)
else:
    p = n//2
    print(y[p-1]-x[p-1]+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

As.sort()
Bs.sort()

if N % 2 == 1:
  i = (N+1) // 2
  print(Bs[i-1] - As[i-1] + 1)
else:
  lower = N // 2
  upper = lower + 1
  print(Bs[upper - 1] - As[lower - 1] + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
AX = [A[i][0] for i in range(N)]
BX = [A[i][1] for i in range(N)]
AX.sort()
BX.sort()
if N % 2 == 1:
  L = AX[(N-1)//2]
  R = BX[(N-1)//2]
  print(R-L+1)
else:
  L = AX[N//2] + AX[N//2]
  R = BX[N//2] + BX[N//2]
  print(R-L+1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

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


def main():
    n = ni()
    bo = []
    up = []
    for _ in range(n):
        a,b = na()
        bo += [a]
        up += [b]
    bo.sort()
    up.sort()
    
    if n%2 == 1:
        print(up[n//2] - bo[n//2] + 1)
    else:
        pre_b, pre_u = bo[n//2 - 1], up[n//2 - 1]
        nex_b, nex_u = bo[n//2], up[n//2]
        print((pre_u+nex_u) - (pre_u+pre_b) + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())

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

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
AA = [0]*N
BB = [0]*N
for i in range(N):
  AA[i], BB[i] = map(int,input().split())
AA_sorted = sorted(AA)
BB_sorted = sorted(BB,reverse=True)
if N%2 == 1:
  idx = int(N/2)
  N_Max = BB_sorted[idx]
  N_Min = AA_sorted[idx]
  print(N_Max-N_Min+1)
else:
  idx = int(N/2)
  N_Max = BB_sorted[idx-1]
  N_Min = AA_sorted[idx-1]
  print((N_Max-N_Min)*2-1)