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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(((ri[n//2]) - le[n//2-1]+1)//2)

Submission status: Wrong Answer

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

min_s.sort()
max_s.sort()
if n % 2 == 0:
    min_med = (min_s[n//2-1] + min_s[n//2-1])/2
    max_med = (max_s[n//2-1] + max_s[n//2-1])/2
    print(int((max_med-min_med)*2+1))

else:
    min_med = min_s[(n+1)//2-1]
    max_med = max_s[(n+1)//2-1]

    print(int((max_med-min_med)+1))

Submission status: Wrong Answer

Solution code:
from math import ceil

def cal(AB,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:
        return max(0,B[N//2]-A[N//2]+1)
    else:
        x_min = int((A[(N-1)//2]+A[(N-1)//2+1])/2)
        x_max = ceil((B[(N-1)//2]+B[(N-1)//2+1])/2)
        diff = (x_max-x_min)+1
        return max(0,diff)

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

    ans = cal(AB,N)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if n%2==0:
    min_sum = x[(n//2)-1][0]+x[(n//2)][0]/2
    max_sum = x[(n//2)-1][1]+x[(n//2)][1]/2
    print(int((max_sum-min_sum)*2))
else:
    tmp = x[n//2]
    print(tmp[1]-tmp[0]+1)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
AA = sorted(A)
BB = sorted(B)

if N%2==1:
    low = AA[N//2  ]
    high = BB[N//2  ]
    print(high - low +1)

else:
    low = (AA[N//2-1] + AA[N//2]) / 2
    high = (BB[N//2-1] + BB[N//2]) / 2
    #print(low,high)
    count=0
    while True:
        low +=  0.5
        count+=1
        if low>=high:
            break
    #low = math.floor(low)
    #high = math.ceil(high)
    print(count+1)

Submission status: Wrong Answer

Solution code:
from statistics import median

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

a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]

if n % 2 == 0:
    ma, mb = median(a), median(b)
    print(int(mb - ma) * 2 + 1)
if n % 2 == 1:
    ma, mb = median(a), median(b)
    print(int(mb - ma + 1))

Submission status: Wrong Answer

Solution code:
from statistics import median

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

a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]

if n % 2 == 0:
    ma, mb = median(a), median(b)
    print(ma,mb)
    print(int(mb - ma) * 2 + 1)
if n % 2 == 1:
    ma, mb = median(a), median(b)
    print(int(mb - ma + 1))

Submission status: Wrong Answer

Solution code:
import sys
import copy

def odd(N, AB):
    ans = []
    AB.sort()
    half = []
    for _, i_B in AB[(N+1)//2-1:]:
        half.append(i_B) 
    min_b = min(half)
    for i in range(AB[(N+1)//2-1][0], min_b+1):
        ans.append(i)

    AB.sort(key=lambda  x: x[1], reverse=True)
    half = []
    for i_A, _ in AB[(N+1)//2-1:]:
        half.append(i_A)
    max_a = max(half)
    for i in range(max_a, AB[(N+1)//2-1][1]+1):
        ans.append(i)

    ans = set(ans)
    ans = len(ans)
    return ans

def even(N, AB):
    ans = []
    AB.sort()
    half = []
    for _, i_B in AB[N//2-1:]:
        half.append(i_B) 
    min_b = min(half)
    start = (AB[N//2-1][0] + AB[N//2][0])//2
    if (AB[N//2-1][0] + AB[N//2][0]) % 2 == 1:
        ans.append(start+0.5)
        start += 1
    for i in range(start, min_b+1):
        ans.append(i)
        ans.append(i+0.5)

    AB.sort(key=lambda  x: x[1], reverse=True)
    half = []
    for i_A, _ in AB[N//2-1:]:
        half.append(i_A)
    max_a = max(half)
    end = (AB[N//2-1][1] + AB[N//2][1])//2
    for i in range(max_a, end):
        ans.append(i)
        ans.append(i+0.5)
    else:
        if max_a == end:
            i = max_a
        if (AB[N//2-1][1] + AB[N//2][1]) % 2 == 0:
            ans.append(i+1)

    ans = set(ans)
    ans = len(ans)
    return ans

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

    if N % 2 == 0:
        ans = even(N, AB)
    else:
        ans = odd(N, AB)
    
    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import heapq
input = lambda: sys.stdin.readline().rstrip()

INF = 10**9 + 1


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

    As = sorted(A)
    Bs = sorted(B)

    if N % 2 == 0:
        i1 = N // 2
        i2 = N // 2 - 1
        low = (As[i1] + As[i2]) / 2
        up = (Bs[i1] + B[i2]) / 2
        ans = (up - low) * 2 + 1
        print(int(ans))
    else:
        i = (N - 1) // 2
        low = As[i]
        up = Bs[i]
        ans = up - low + 1
        print(ans)
        exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
AA = sorted(A)
BB = sorted(B)

if N%2==1:
    low = AA[N//2  ]
    high = BB[N//2  ]
    print(high - low +1)

else:
    low = (AA[N//2-1] + AA[N//2]) / 2
    high = (BB[N//2-1] + BB[N//2]) / 2
    count=0
    while True:
        low = low+ 0.5*count
        count+=1
        if low>high:
            break
    #low = math.floor(low)
    #high = math.ceil(high)
    print(count)

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 = sorted( A )
B = sorted( B )

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

up = sorted(ab,key=lambda a:a[0],reverse=True)
down = sorted(ab,key=lambda a:a[1],reverse=True)

if N%2 == 1:
    print(up[N//2][1]-down[N//2][0]+1)
else:
    r = (up[N//2-1][1]+up[N//2][1])
    l = (down[N//2-1][0]+down[N//2][0])
    print(r-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 )

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

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

Submission status: Wrong Answer

Solution code:
from math import ceil
from heapq import heappush as p
n=int(input())
A=[]
B=[]
c=ceil(n//2)
for i in range(n):
  a,b=map(int,input().split())
  p(A,a)
  p(B,b)
if n%2:
  print(B[c]-A[c]+1)
else:
  print(int(((B[c]+B[c-1])/2-(A[c]+A[c-1])/2)//0.5+1))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

up = sorted(ab,key=lambda a:a[0])
down = sorted(ab,key=lambda a:a[1])
if N%2 == 1:
    print(up[N//2][1]-down[N//2][0]+1)
else:
    r = (up[N//2-1][1]+up[N//2][1])
    l = (down[N//2-1][0]+down[N//2][0])
    print(r-l+1)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


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:
    ans = B[N//2] - A[N//2]+1
    print(ans)
else:
    vmin = A[N//2]+A[N//2]+1
    vmax = B[N//2]+B[N//2]+1
    ans = vmax-vmin+1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

up = sorted(ab,key=lambda a:a[0],reverse=True)
down = sorted(ab,key=lambda a:a[1],reverse=True)
if N%2 == 1:
    print(up[N//2][1]-down[N//2][0]+1)
else:
    r = (up[N//2-1][1]+up[N//2][1])
    l = (down[N//2-1][0]+down[N//2][0])

    print(r-l+1)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
AA = sorted(A)
BB = sorted(B)

if N%2==1:
    low = AA[N//2  ]
    high = BB[N//2  ]
    print(high - low +1)

else:
    low = (AA[N//2-1] + AA[N//2]) / 2
    high = (BB[N//2-1] + BB[N//2]) / 2
    low = math.floor(low)
    high = math.ceil(high)
    print(high - low +1)

Submission status: Wrong Answer

Solution code:
import math

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

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

ans = 0
if isinstance(mid_a, float):
    if not mid_a.is_integer():
        ans += 1
        mid_a = math.ceil(mid_a)
if isinstance(mid_b, float):
    if not mid_b.is_integer():
        ans += 1
        mid_b = math.floor(mid_b)

ans += mid_b - mid_a + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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

ans = 0
if isinstance(mid_a, float):
    if not mid_a.is_integer():
        ans += 1
        mid_a = math.ceil(mid_a)
if isinstance(mid_b, float):
    if not mid_b.is_integer():
        ans += 1
        mid_b = math.floor(mid_b)
print(mid_b - mid_a + 1)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


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:
    ans = B[-2] - A[1]+1
    print(ans)
else:
    print(-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)
if N%2:
    ans=int(mB-mA)+1
else:
    if mA//1==mA and mB//1==mB:
        ans=int(mB-mA)*2-1
    elif mA//1!=mA and mB//1==mB:
        ans=(mB-(mA//1))*2
    elif mA//1==mA and mB//1!=mB:
        ans=((mB//1+1)-mA)*2
    else:
        ans=int(mB-mA)*2+1
print(int(ans))

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:
  # 奇数の場合
  Amid = A[N // 2]
  Bmid = B[N // 2]
  print(Bmid - Amid + 1)
else:
  # 偶数の場合
  Amid = (A[N // 2] + A[(N // 2) - 1]) / 2
  Bmid = (B[N // 2] + B[(N // 2) - 1]) / 2
  print(int(Bmid - Amid) * 2 + 1)

Submission status: Wrong Answer

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

AB.sort()
if N % 2 == 0:
  l1 = AB[N//2][0] 
  l2 = AB[N//2 - 1][0]
else:
  l = AB[N//2][0]
AB.sort(key = lambda x: x[1])
if N % 2 == 0:
  r1 = AB[N//2][1] 
  r2 = AB[N//2 - 1][1]
else:
  r = AB[N//2][1]
  
if N % 2 == 0:
  ans = (r1 + r2) - (l1 + l2)
  ans *= 2
  ans -= 1
  print(ans)
else:
  print(r - l + 1)

Submission status: Wrong Answer

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:
        u = a[N//2-1] + a[N//2]
        v = b[N//2-1] + b[N//2]
        return max(int(v/2-u/2)*2+1, 0)
    else:
        u = a[(N)//2]
        v = b[(N)//2]
        return max(v-u+1, 0)

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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_b+pre_b) + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from statistics import median

n = int(input())

a = []
b = []

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

print(median(b) - median(a) + 1)

Submission status: Wrong Answer

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

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

A = []
B = []
for a, b in ab:
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if N % 2 == 0:
    a1 = A[N // 2 - 1]
    b1 = B[N // 2 - 1]
    a2 = A[N // 2]
    b2 = B[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(int((xb - xa) * 2 + 1))
    print("dummy")
else:
    xa = A[N // 2]
    xb = B[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


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

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


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

Submission status: Wrong Answer

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

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

A = []
B = []
for a, b in ab:
    A.append(a)
    B.append(b)

A.sort()
B.sort

if N % 2 == 0:
    a1 = A[N // 2 - 1]
    b1 = B[N // 2 - 1]
    a2 = A[N // 2]
    b2 = B[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(int((xb - xa) * 2 + 1))
else:
    xa = A[N // 2]
    xb = B[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

Solution code:
def main():

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

    a = sorted(AB)
    # b = sorted(AB, key = lambda x: x[1])

    x, y = a[0]
    i = 0
    max_y = y
    while i < (N+1)//2:
        z, w = a[i]
        if z > y:
            x, y = z, w
            max_y = y
        elif z <= max_y:
            x, y = z, min(y, w)
            max_y = max(y, max_y)
        i += 1

    # print(x, y)
    if N % 2 == 1:
        return y - x + 1
    return (y-x+1) + (y-x)

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print((ri[n//2] - le[n//2-1])//2+1)

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(int((xb - xa) * 2 + 1))
else:
    xa, xb = ab[N // 2]
    print("hoge")
    print(xb - xa + 1)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+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 = sorted( A )
B = sorted( B )

if n % 2 == 0:
  i1 = n // 2 - 1
  i2 = n // 2
  print(int(( B[ i2 ] + B[ i1 ] ) / 2 - ( A[ i2 ] + A[ i1 ] ) / 2 )  * 2 + 1 )
else:
  i = ( n + 1 ) // 2 - 1
  print( B[ i ] - A[ i ] + 1 )

Submission status: Wrong Answer

Solution code:
from statistics import median

n = int(input())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
m_a = median(A)
m_b = median(B)
m = int(m_b - m_a)
for tmp in [m_a, m_b]:
    if type(tmp) is float:
        m += 1

if n%2 == 1:
    print(m + 1)
else:
    print(m)

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(int((xb - xa) * 2 + 1))
else:
    xa, xb = ab[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(xa, xb)
    print(int((xb - xa) * 2 + 1))
else:
    xa, xb = ab[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2+1] - le[n//2+1]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2-1]+1)

Submission status: Wrong Answer

Solution code:
def main():

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

    a = sorted(AB)
    # b = sorted(AB, key = lambda x: x[1])

    x, y = a[0]
    i = 1
    max_y = y
    while i < (N+1)//2:
        z, w = a[i]
        if z > y:
            x, y = z, w
            max_y = y
        elif z <= max_y:
            x, y = z, min(y, w)
            max_y = max(w, max_y)
        i += 1

    # print(x, y)
    if N % 2 == 1:
        return y - x + 1
    return (y-x+1) + (y-x+1) // 2

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print((xb - xa) * 2 - 1)
else:
    xa, xb = ab[N // 2]
    print(xb - xa + 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:
    AA = A[(N+1)//2]
    BB = B[(N+1)//2-1] 
    print(BB-AA+1)
else:
    AA = (A[N//2-1]+A[N//2])//2
    BB = (B[N//2-2]+B[N//2-2])//2
    print(BB-AA+1)

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(xa, xb)
    print((xb - xa) * 2 - 1)
else:
    xa, xb = ab[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

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

if n%2==0:
    min_sum = x[(n//2)-1][0]+x[(n//2)][0]
    max_sum = x[(n//2)-1][1]+x[(n//2)][1]
    print(int((max_sum-min_sum+1)/2//0.5))
else:
    tmp = x[n//2]
    print(len(range(tmp[0], tmp[-1]+1)))

Submission status: Wrong Answer

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

if n%2==0:
    min_sum = x[(n//2)-1][0]+x[(n//2)][0]
    max_sum = x[(n//2)-1][1]+x[(n//2)][1]
    print(int((max_sum-min_sum)+1/2//0.5))
else:
    tmp = x[n//2]
    print(len(range(tmp[0], tmp[-1]+1)))

Submission status: Wrong Answer

Solution code:
from math import *
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)
A.sort();B.sort()
if N%2:
    ans=median(B)-median(A)+1
else:
    ans=(median(B)-median(A))*2+1
print(ans)

Submission status: Wrong Answer

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

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

ab.sort()

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    a1, b1 = ab[N // 2 - 1]
    a2, b2 = ab[N // 2]
    xa = (a2 - a1) / 2
    xb = (b2 - b1) / 2
    print((xb - xa) * 2 - 1)
else:
    xa, xb = ab[N // 2]
    print(xb - xa + 1)

Submission status: Wrong Answer

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

l = 0
r = 0

AB.sort()
if N % 2 == 0:
  l = AB[N//2][0] + AB[N//2 - 1][0]
else:
  l = AB[N//2][0]
AB.sort(key = lambda x: x[1])
if N % 2 == 0:
  r = AB[N//2][1] + AB[N//2 - 1][0]
else:
  r = AB[N//2][1]
  
if N % 2 == 0:
  print((r - l) * 2 + 1)
else:
  print(r - l + 1)

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    ab = [map(int, input().split()) for _ in range(n)]
    a, b = [list(i) for i in zip(*ab)]
    new_a = sorted(a)
    new_b = sorted(b, reverse=True)
    if n % 2 == 1:
        min_m = new_a[(n + 1) // 2 - 1]
        max_m = new_b[(n + 1) // 2 - 1]
        print((max_m - min_m)  + 1)
    else:
        min_m = (new_a[n // 2 - 1] + new_a[n // 2 + 1 - 1]) // 2
        max_m = (new_b[n // 2 - 1] + new_b[n // 2 + 1 - 1]) // 2
        print((max_m - min_m) * 2 + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n%2==0:
    min_sum = x[(n//2)-1][0]+x[(n//2)][0]
    max_sum = x[(n//2)-1][1]+x[(n//2)][1]
    print(int((max_sum-min_sum)/2//0.5)+1)
else:
    tmp = x[n//2]
    print(len(range(tmp[0], tmp[-1]+1)))

Submission status: Wrong Answer

Solution code:
def main():

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

    a = sorted(AB)
    # b = sorted(AB, key = lambda x: x[1])

    x, y = a[0]
    i = 1
    while i < (N+1)//2:
        z, w = a[i]
        if z > y:
            x, y = z, w
        elif x <= z <= y:
            x, y = z, min(y, w)
        i += 1

    # print(x, y)
    if N % 2 == 1:
        return y - x + 1
    return (y-x+1) + (y-x+1) // 2

if __name__ == '__main__':
    print(main())