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:
import sys

input = sys.stdin.readline


def main():
    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 == 0:
        a = A[N // 2 - 1]
        b = B[N // 2]
        ans = 2 * (b - a) - 1
    else:
        a = A[N // 2]
        b = B[N // 2]
        ans = b - a + 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if N % 2 == 1:
  x = int((N + 1)// 2)
  ans = abs(B[x - 1] - A[x - 1]) + 1
else:
  x = int(N // 2)
  a = max(A[x], B[x])
  b = min(A[x - 1], B[x - 1])
  ans = abs(b - a) + 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
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ABlist = [list(map(int, input().split())) for _ in range(N)]
ABlist.sort()
def sa(arr):
    return arr[1] - arr[0]
if N % 2 == 1:
    print(sa(ABlist[(N+1)//2-1])+1)
else:
    print(sa(ABlist[N//2-1]) + sa(ABlist[N//2]) + 1)

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

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])
	# if (l[0][1]<l[1][0]) or (l[1][1]<l[0][0]):
	print(l[0][1]-l[0][0]+l[1][1]-l[1][0]+1)
	# else:

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)


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

Submission status: Wrong Answer

Solution code:
N=int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
a,b = zip(*ab)
res = 0
ma = max(b)+1
# 左端
def solve_left(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2:
        return False
    return True

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

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

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

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

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 midA < max(A):
    ans += math.ceil(max(A) - midA)
if midB > min(B):
    ans += math.ceil(midB - min(B))
print(ans)

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:
    mid_l = [a[n//2-1], a[n//2]]
    mid_r = [b[n//2-1], b[n//2]]
    l = mid_l[0] + mid_r[0]
    r = mid_r[1] + mid_r[1]
    print(r - l)
else:
    mid_l = a[n//2]
    mid_r = b[n//2]
    print(mid_r - mid_l + 1)

Submission status: Wrong Answer

Solution code:
def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi (mn<=i<mx)
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx

def C(x):
    c = 0
    for a, b in X:
        if x <= b:
            c+=1
    return c
def C2(x):
    c = 0
    for a, b in X:
        if a <= x:
            c+=1
    return c

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

n = bsearch(-1, 10**9, lambda x : C(x)<(N+1)//2)
n2 = bsearch(-1, 10**9, lambda x : C2(x)>=(N+1)//2)
#print(C(100))


print(n-n2)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
seg = [list(map(int, input().split())) for _ in range(n)]
a = [x[0] for x in seg]
b = [x[1] for x in seg]
a.sort()
b.sort()

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

Submission status: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)]
    if N%2 == 1:
        print(L[N//2][1]-L[N//2][0]+1)
    else:
        a = L[N//2-1][0]+L[N//2][0]
        b = L[N//2-1][1]+L[N//2][1]
        print(b-a+1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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

if n % 2 == 1:
    info = sorted(info)
    l = info[n // 2][0]
    info = sorted(info)[::-1]
    r = info[n // 2][1]
    print(r - l + 1)
    
else:
    info = sorted(info)
    l, lmax = info[n // 2 - 1]
    info = sorted(info)[::-1]
    rmin, r = info[n // 2 - 1]
    if rmin <= lmax:
        print(r * 2 - l * 2 - 1)
    else:
        print(r * 2 - l * 2 - (rmin - lmax) - 1)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n%2==1:
    for i in range(n):
        sr=input()
        if i==n//2:
            a,b=map(int,sr.split( ))
    print(b-a+1)
else:
    for i in range(n):
        sr=input()
        if i==n/2-1:
            a,b=map(int,sr.split( ))
        if i==n/2:
            c,d=map(int,sr.split( ))
    print(b+d-c-a+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 d >= c:
        l = m
    else:
        r = m
    # print(l,r,m,c,d)
    m = (l+r)//2
# print(l)
aa = l

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 d >= c:
        r = m
    else:
        l = m
    # print(l,r,m,c,d)
    m = (l+r)//2
# print(r)
bb = r
ans = aa-bb+1
if n%2 == 1:
    ans =(ans+1)//2
print(ans)

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))
        print(ma[N // 2] - mi[N // 2] + 2)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def f(n):
  AB = list(zip(A, B))
  AB.sort()
  return AB[n]

if N%2==0:
  a1, b1 = f(N//2-1)
  a2, b2 = f(N//2)
  print((b1+b2)-(a1+a2)+1)
else:
  a, b = f(N//2)
  print(b-a+1)

Submission status: Wrong Answer

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


def ch(i):
    x = 0
    y = 0
    z = 0
    for a, b in ab:
        if a <= i <= b:
            y += 1
        elif b < i:
            x += 1
        else:
            z += 1
    return x, y, z


if n % 2 == 1:
    n2 = n // 2

    mi = 1
    ma = 10 ** 9
    while mi != ma:
        mm = (mi + ma) // 2
        x, y, z = ch(mm)
        if x + y - 1 >= n2:
            ma = mm
        else:
            mi = mm + 1
    a = mi

    mi = 1
    ma = 10 ** 9
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        x, y, z = ch(mm)
        if z + y - 1 >= n2:
            mi = mm
        else:
            ma = mm - 1
    b = mi
    print(b - a + 1)
else:
    n2 = n // 2

    mi = 0
    ma = 10 ** 9+1
    while mi != ma:
        mm = (mi + ma) // 2
        x, y, z = ch(mm)
        if x + y - 1 >= n2:
            ma = mm
        else:
            mi = mm + 1
    a1 = mi

    mi = 0
    ma = 10 ** 9+1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        x, y, z = ch(mm)
        if z + y - 1 >= n2:
            mi = mm
        else:
            ma = mm - 1
    b1 = mi

    n2 = n // 2 - 1

    mi = 0
    ma = 10 ** 9+1
    while mi != ma:
        mm = (mi + ma) // 2
        x, y, z = ch(mm)
        if x + y - 1 >= n2:
            ma = mm
        else:
            mi = mm + 1
    a2 = mi

    mi = 0
    ma = 10 ** 9+1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        x, y, z = ch(mm)
        if z + y - 1 >= n2:
            mi = mm
        else:
            ma = mm - 1
    b2 = mi
    print(b1 + b2 - a1 + a2 - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
left = sum(A)
right = sum(B)
if N%2 == 0:
  print(right-left+1)
else:
  A.sort()
  B.sort()
  print(B[(N-1)//2]-A[(N-1)//2]+1)

Submission status: Wrong Answer

Solution code:
n,*ab = map(int,open(0).read().split())
a = ab[::2]
b = ab[1::2]
a.sort()
b.sort(reverse=True)

if n%2 == 1:
    med_min = a[(n-1)//2]
    med_max = b[(n-1)//2]
    ans = med_max - med_min + 1
else:
    med_min = (a[n//2-1] + a[n//2] ) /2
    med_max = (b[n//2-1] + b[n//2] ) /2
    ans = (med_max - med_min)*2 + 1

print(ans)

Submission status: Wrong Answer

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
AB=n3(n)
A=[x[0] for x in AB]
B=[x[1] for x in AB]

if n%2==0:
    a1,a2=A[n//2-1],A[n//2]
    b1,b2=B[n//2-1],B[n//2]
    a=(a1+a2)/2
    b=(b1+b2)/2
    ans=int((b-a)*2)+1
else:
    a=A[n//2]
    b=B[n//2]
    ans=b-a+1
print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret
def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while(True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret

def solve():
    n = getN()
    nums = []
    for i in range(n):
        nums.append(getList())

    if n % 2 == 1:
        nums.sort()
        med = nums[(n+1)//2-1][0]
        nums.sort(key=lambda x: x[1])
        medhigh = nums[(n+1)//2-1][1]

        print(medhigh - med + 1)
    else:
        nums.sort()
        med = (nums[n // 2 - 1][0] + nums[n // 2][0]) / 2
        nums.sort(key=lambda x: x[1])
        medhigh = (nums[n // 2 - 1][1] + nums[n // 2][1]) / 2

        print(int(medhigh - med * 2) + 1)

def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
a,b = zip(*ab)
res = 0
ma = max(b)+1
# 左端
def solve_left(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2:
        return False
    return True

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

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

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

res = (res_right-res_left) + 1
print(res)

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)

if N % 2 == 0:
    ans = 2*(pts[-2] - pts[1] + 1) + 1
else:
    ans = pts[-2] - pts[1] + 1
print(ans)

Submission status: Wrong Answer

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


ab.sort()
# print(ab)
if n%2==0:
    # print((ab[n//2][0]+ab[n//2-1][0])/2)
    tmp1=(ab[n//2][0]+ab[n//2-1][0])/2
else:
    # print(ab[n//2][0])
    tmp1=ab[n//2][0]

ab.sort(key=lambda x: x[1])
# print(ab)
if n%2==0:
    # print((ab[n//2][1]+ab[n//2-1][1])/2)
    tmp2=(ab[n//2][1]+ab[n//2-1][1])/2
    print(int(tmp2-tmp1)*2+1)
else:
    # print(ab[n//2][1])
    tmp2=ab[n//2][1]
    print(tmp2-tmp1+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
if N%2==0:
    for i in range(1,N+1):
        A,B=map(int,input().split())
        if i==N//2:
            A0=A
        if i==N//2+1:
            B0=B
            ans=B0-A0+1
else:
    for i in range(1,N+1):
        A,B=map(int,input().split())
        if i==(N+1)//2:
            ans=B-A+1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
bounds = [list(map(int, input().split())) for _ in range(n)]
upper = [b[1] for b in bounds]
lower = [b[0] for b in bounds]

if n % 2 == 0:
	u_mid2 = upper[n // 2 - 1] + upper[n // 2]
	l_mid2 = lower[n // 2 - 1] + lower[n // 2]
	print(u_mid2 - l_mid2 + 1)
else:
	print(upper[n // 2] - lower[n // 2] + 1)

Submission status: Wrong Answer

Solution code:
n,*ab = map(int,open(0).read().split())
a = ab[::2]
b = ab[1::2]
a.sort()
b.sort(reverse=True)

if n%2 == 1:
    med_min = a[(n-1)//2]
    med_max = b[(n-1)//2]
    ans = med_max - med_min + 1
else:
    med_min = (a[n//2-1] + a[n//2] ) //2
    med_max = (b[n//2-1] + b[n//2] ) //2
    ans = (med_max - med_min)*2 + 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve_even(n, aaa, bbb):
    li = n // 2 - 1
    ri = n // 2
    aaa.sort()
    bbb.sort()
    ll = aaa[li]
    lr = aaa[ri]
    rl = bbb[li]
    rr = bbb[ri]
    return (rr + lr) - (rl + ll) + 1


def solve_odd(n, aaa, bbb):
    k = n // 2
    aaa.sort()
    bbb.sort()
    return bbb[k] - aaa[k] + 1


n, *ab = map(int, sys.stdin.buffer.read().split())
if n % 2 == 0:
    ans = solve_even(n, ab[0::2], ab[1::2])
else:
    ans = solve_odd(n, ab[0::2], ab[1::2])
print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret
def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while(True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret

def solve():
    n = getN()
    nums = []
    for i in range(n):
        nums.append(getList())

    if n % 2 == 1:
        nums.sort()
        med = nums[(n+1)//2-1][0]
        nums.sort(key=lambda x: x[1])
        medhigh = nums[(n+1)//2-1][1]

        print(medhigh - med + 1)
    else:
        nums.sort()
        med = (nums[n // 2 - 1][0] + nums[n // 2][0]) / 2
        nums.sort(key=lambda x: x[1])
        medhigh = (nums[n // 2 - 1][1] + nums[n // 2][1]) / 2

        print(int(medhigh - med) * 2 + 1)

def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

A, B = map(list, zip(*AB))
A.sort()
B.sort()

ng, ok = 0, 10 ** 9 + 10
while ok - ng > 1 :
  mid = (ok + ng) // 2
  if N - bisect_right(A, mid) >= N // 2 + 1 :
    ng = mid
  else :
    ok = mid

ret = -ok

ok, ng = 0, 10 ** 9 + 10
while ng - ok > 1 :
  mid = (ok + ng) // 2
  if bisect_left(B, mid) >= N // 2 + 1 :
    ng = mid
  else :
    ok = mid
    
ret += ok + 1

print(max(0, ret))