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

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

# A.sort()
# B.sort()
if N%2 == 1:
    X.sort(key=lambda x: x[0])
    min_range = [X[N//2][0], X[N//2+1][1]]
    
    X.sort(key=lambda x: x[1])
    max_range = [X[N//2-1][0], X[N//2][1]]
    diff = 0
    if min_range[1] >= max_range[0]:
        diff = min_range[1] - max_range[0] +1
    print(min_range[1]-min_range[0] +max_range[1]-max_range[0] -diff +2)
else:
    if N == 2:
        X.sort(key=lambda x: x[0])
        min_m = (X[N//2-1][0] +X[N//2][0])/2
        X.sort(key=lambda x: x[1])
        max_m = (X[N//2-1][1] +X[N//2][1])/2
        print(int((max_m -min_m)//0.5 +1))
    else:
        X.sort(key=lambda x: x[0])
        min_range_l = [X[N//2-1][0], min(X[N//2-1][1], X[N//2+1][1])]
        min_range_r = [X[N//2][0], min(X[N//2][1], X[N//2+1][1])]
        min_l = (min_range_l[0] +min_range_r[0])/2
        min_r = (min_range_l[1] +min_range_r[1])/2
        min_range = [min_l, min_r]
        
        X.sort(key=lambda x: x[1])
        max_range_l = [max(X[N//2-1][0], X[N//2-2][1]), X[N//2-1][1]]
        max_range_r = [max(X[N//2][0], X[N//2-2][1]), X[N//2][1]]
        max_l = (max_range_l[0] +max_range_r[0])/2
        max_r = (max_range_l[1] +max_range_r[1])/2
        max_range = [max_l, max_r]

        diff = 0
        if min_range[1] >= max_range[0]:
            diff = min_range[1] - max_range[0] +1
        print(min_range[1]-min_range[0] +max_range[1]-max_range[0] -diff +2)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

START = 0
END = 1
intervals = []
for i in range(N):
    start, end = [int(s) for s in input().split()]
    intervals.append((start, START, i))
    intervals.append((end, END, i))

sortedIntervals = sorted(intervals)
setIntervals = set(intervals)

if N % 2 == 1:
    startCount = 0
    endCount = 0
    rangeStart = None
    rangeEnd = None
    for x, label, index in sortedIntervals:
        if label == START:
            startCount += 1
            if startCount == (N + 1) // 2:
                rangeStart = x
        else:
            endCount += 1
            if endCount == (N + 1) // 2:
                rangeEnd = x 
    print(rangeEnd - rangeStart + 1)
else:
    startCount = 0
    endCount = 0
    rangeStart1 = None
    rangeEnd1 = None
    rangeStart2 = None
    rangeEnd2 = None
    for x, label, index in sortedIntervals:
        if label == START:
            startCount += 1
            if startCount == N // 2:
                rangeStart1 = x
            elif startCount == N // 2 + 1:
                rangeStart2 = x
        else:
            endCount += 1
            if endCount == N // 2:
                rangeEnd1 = x 
            elif endCount == N // 2 + 1:
                rangeEnd2 = x
    if rangeStart1 == rangeEnd1:
        print(rangeEnd2 - rangeStart2 + 1)
    elif rangeStart2 == rangeEnd2:
        print(rangeEnd1 - rangeStart1 + 1)
    elif rangeEnd1 == rangeStart2 and (rangeEnd1,  rangeStart2) in setIntervals:
        print(rangeEnd2 - rangeStart1 + 1)
    else:
        start = (rangeStart1 + rangeStart2)
        end = (rangeEnd2 + rangeStart2)
        result = (end - start) + 1
        print(result)

Submission status: Wrong Answer

Solution code:

import statistics
import math

n = int(input())

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

#a.sort()
#b.sort()

print(int(statistics.median(b)+0.5)- int(statistics.median(a)) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append([x, y])
    b.append([y, x])
a = sorted(a)
b = sorted(b, reverse = True)

if n % 2 ==0:
    s = a[n//2 -1][0]
    e = b[n//2 -1][0]
    ans = 2*(e-s+1)-3
    
    
    if n//2>=0 and n//2+1<=n-1:
        if a[n//2][0] ==s or a[n//2+1][0]  ==s:
            ans += 1
    elif n//2>=0:
        if a[n//2][0] ==s:
            ans += 1
    else:
        if a[n//2+1][0]  ==s:
            ans += 1
    
    
    if n//2>=0 and n//2+1<=n-1:
        if b[n//2][0] ==e or [n//2+1][0] ==e:
            ans += 1
    elif n//2>=0:
        if  b[n//2][0] ==e:
            ans += 1
    else:
        if [n//2+1][0] ==e:
            ans += 1
    print(ans)
    
    
else:
    
    
    
    s = a[(n+1)//2 -1][0]
    e = b[(n+1)//2 -1][0]
    ans = e-s+1
  
    if (n+1)//2>=0 and (n+1)//2 +1<=n-1:
        if a[(n+1)//2][0] ==s or a[(n+1)//2 +1][0]  ==s:
            ans += 1
    elif (n+1)//2>=0:
        if a[(n+1)//2][0] ==s:
            ans += 1
    else:
        if a[(n+1)//2 +1][0]  ==s:
            ans += 1

    if n//2>=0 and n//2+1<=n-1:
        if b[(n+1)//2][0] ==e or [(n+1)//2 +1][0] ==e:
            ans += 1
    elif n//2>=0:
        if  b[(n+1)//2][0] ==e:
            ans += 1
    else:
        if [(n+1)//2 +1][0] ==e:
            ans += 1

    print(ans)

Submission status: Wrong Answer

Solution code:
import statistics
import math
from decimal import *
N = int(input())

n =[]
m =[]

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

nmean = Decimal(statistics.median(n))
mmean =Decimal(statistics.median(m))

if N%2 == 1:
    print(mmean - nmean + 1)
else:
    print(int(mmean - nmean)*2 +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)

if N % 2 != 0:
  m = sorted(A)[int(N/2)]
  M = sorted(B)[int(N/2)]
else:
  m = sorted(A)[int(N/2) - 1]
  M = sorted(B)[int(N/2)]
  
print(M - m + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

amax=0
bmin=10**100
arra=[]
arrb=[]
for i in range(n):
    a,b=mii()
    arra.append(a)
    arrb.append(b)

arra.sort()
arrb.sort()

if n%2==1:
    p=arra[n//2 ]
    q=arrb[n//2 ]

    print(q-p+1)
else:
    p=(arra[n//2 -1]+arra[n//2])/2
    q=(arrb[n//2 -1]+arra[n//2])/2
    print(q-p+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)

A = sorted(A)
B = sorted(B)
num = int(n/2)

if n%2 == 0:
  A_c = (A[num]+A[num-1])/2
  B_c = (B[num]+B[num-1])/2
  print(int((A_c-B_c)*2+1))

else:
  A_c = A[num]
  B_c = B[num]
  print(B_c - A_c+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
L1 = []
L2 = []

for _ in range(N):
    a,b = map(int,input().split())
    L1.append(a)
    L2.append(b)

L1.sort()
L2.sort()

def median(L):
    if N&1:
        return L[(N)//2]
    else:
        ret = L[N//2-1] + L[N//2]
        return ret/2

ans = median(L2) - median(L1)
ans = int(ans//1)
if N%2==0:
    ans *= 2
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math


def median(array):
    if N % 2:
        return array[N // 2]
    else:
        return sum(array[N // 2 - 1: N // 2 + 1]) / 2


N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
x = median(A)
y = median(B)
if N % 2:
    print(y - x + 1)
else:
    temp = math.floor(y) - math.floor(x)
    print(2 * temp + 1)

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])/2
    q = (B[n//2] + B[n//2-1])/2
    print(int((q-p)*2+1))

Submission status: Wrong Answer

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

X.sort(key=lambda x:x[0])
x=[[X[0][0],X[0][1]]]
for i in range(1,N):
    a=X[i][0]
    b=X[i][1]
    if x[-1][1]<a:
        x.append([a,b])
    elif x[-1][1]<b:
        x[-1][1]=b

A.sort()
B.sort()
ans=0
if N%2==1:
    MIN=A[N//2]
    MAX=B[N//2]
    if MAX>x[0][1]:
        ans+=x[0][1]-MIN+1
    else:
        ans+=MAX-MIN+1
        print(int(ans))
        exit()
    for i in range(1,len(x)):
        MIN=x[i][0]
        if MAX>x[i][1]:
            ans+=x[i][1]-MIN+1
        elif MAX<MIN:
            break
        else:
            ans+=MAX-MIN+1
            break
    print(int(ans))
else:
    MIN=(A[N//2-1]+A[N//2])/2
    MAX=(B[N//2-1]+B[N//2])/2
    if MAX>x[0][1]:
        ans+=(x[0][1]-MIN)*2+1
    else:
        ans+=(MAX-MIN)*2+1
        print(int(ans))
        exit()
    for i in range(1,len(x)):
        MIN=x[i][0]
        if MAX>x[i][1]:
            ans+=(x[i][1]-MIN)*2+2
        elif MIN>MAX:
            break
        else:
            ans+=(MAX-MIN)*2+2
            break
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import math


def median(array):
    if N % 2:
        return array[N // 2]
    else:
        return sum(array[N // 2 - 1: N // 2 + 1]) / 2


N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
x = median(A)
y = median(B)
if N % 2:
    print(y - x + 1)
else:
    temp = math.ceil(y) - math.floor(x)
    print(2 * temp + 1)

Submission status: Wrong Answer

Solution code:
# import sys
#
#
# RS = lambda: sys.stdin.readline()[:-1]
# RI = lambda x=int: x(RS())
# RA = lambda x=int: map(x, RS().split())
# RSS = lambda: RS().split()
import statistics
m = statistics.median


def solve(ab):
    # allowed = []
    mini = m(a)
    maxi = m(b)
    ab.sort(key=lambda x: x[0])
    ab2= []
    l = ab[0][0]
    r = ab[0][1]
    for i in range(n-1):
        r = max(ab[i][1], r)
        if r < ab[i+1][0]:
            ab2.append([l, r])
            l = ab[i+1][0]

    r = max(ab[n-1][1], r)
    ab2.append([l,r])
    ab3 = []
    for ai in ab2:
        l = max(ai[0], mini)
        r = min(ai[1], maxi)
        if l<r:
            ab3.append([max(ai[0], mini), min(ai[1], maxi)])
    ans = 0
    for el in ab3:
        if n&1:
            ans += el[1]-el[0] + 1
        else:
            ans += 2*(el[1]-el[0]) + 1
    print(int(ans))



    return




a = []
b = []
ab = []
n = int(input())
for i in range(n):
    inp = [int(i) for i in input().split()]
    a.append(inp[0])
    b.append(inp[1])
    ab.append(inp)
solve(ab)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
li = [[0,0] for i in range(n)]
lis.sort(key=lambda x:x[1],reverse=True)
lis.sort(key=lambda x:x[0])
minmin = lis[(n-1)//2][0]
lis.sort(key=lambda x:x[1],reverse=True)
maxmin = lis[(n-1)//2][0]
lis.sort(key=lambda x:x[1],reverse=True)
maxmax = lis[(n-1)//2][1]
lis.sort(key=lambda x:x[0],reverse=True)
minmax = lis[(n-1)//2][1]

  # print(midmin,midmax)

if n % 2 == 1:
    print(maxmax-minmin+1)
else:
    print(min(maxmax-minmin+1,(maxmax-maxmin+1)*(minmax-minmin+1)))
status = 0
midmintonum = []
midmaxtonum = []
inmidleft = []
inmidright = []

Submission status: Wrong Answer

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

ans = 0
lst = []
#Nが偶数のとき
if n % 2 == 0:
    x = s[int(n/2)-1]
    y = s[int(n/2+1)-1]
    for i in range(x[0], x[1]+1):
        for j in range(y[0], y[1]+1):
            if i+j not in lst:
                lst.append(i+j)
                ans +=1
#Nが奇数のとき
elif n % 2 != 0:
    x = s[int(n/2)]
    ans = x[1] - x[0] - 1 + 2        
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

ab = [list(map(int, input().split())) for _ in range(n)]
ab = sorted(ab, key=lambda x:int(x[1]))

c = [ab[i][1]-ab[i][0] for i in range(n)]

if n%2 == 1:
    center = n//2
    answer = ab[center][1]-ab[center][0]+1
else:
    center = [n//2-1,n//2]
    answer1 = ab[center[0]][1] - ab[center[0]][0]+1
    answer2 = ab[center[1]][1] - ab[center[1]][0]+1
    answer = answer1*answer2 - max(0,ab[center[0]][1]-min(ab[center[0]][0],ab[center[1]][1]))

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
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()
A = np.array(A)
B = np.array(B)
print(int(np.median(B) - np.median(A))  + 1)

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])
La=sorted(L)
Lb=sorted(L, key=lambda x: x[1])
if N%2==1:
    
    idx=N//2
    a,b=La[idx]
    Lahalf=L[idx+1:]
    bmin=float("INF")
    for l in Lahalf:
        bmin=min(bmin, l[1])
    MIN1=a
    MIN2=min(b,bmin)

    
    idx=N//2
    a,b=Lb[idx]
    Lbhalf=Lb[:idx]
    amax=0
    for l in Lbhalf:
        amax=max(amax, l[0])
    MAX1=max(a,amax)
    MAX2=b
    #print(MIN1, MIN2, MAX1, MAX2)
    if MIN2<MAX1:
        print(MIN2-MIN1+1+MAX2-MAX1+1)
    else:
        print(MAX2-MIN1+1)
    
else:
    idx=N//2-1
    a,b=La[idx]
    a1,b1=La[idx+1]
    MIN1, MIN2=a,a1

    
    idx=N//2
    a,b=Lb[idx]
    Lbhalf=Lb[:idx]
    _,MAX1=Lb[idx-1]
    MAX2=b
    #print(MIN1, MIN2, MAX1, MAX2)
    if MIN2>=MAX1:
        ans=(MAX2-MIN2)*2+1
    else:

        ans=(MIN2-MIN1)*2+1+(MAX2-MAX1)*2+1

    #print(ans)
    #print(MIN1, MIN2, MAX1, MAX2)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    L = list(zip(*sorted(list(zip(*L)))))
    if N % 2 == 0:
        M = (L[N//2][1]+L[N//2-1][1])/2
        m = (L[N//2][0]+L[N//2-1][0])/2
        print(int((M-m)//0.5+1))
    else:
        M = L[N//2][1]
        m = L[N//2][0]
        for i in L:
            if i[0]==m:
                M=max(M,i[1])
        print(int(M-m+1))


# 
resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0 for _ in range(N)]

for i in range(N):
    a, b = map(int, input().split())
    A[i] = b-a+1

A.sort()
if N%2 == 0:
    print(A[N//2-1]//2+A[N//2])
else:
    print(A[N//2])

Submission status: Wrong Answer

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) * n - (n - 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: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    # s = input()
    n = int(input())
    # a, b = map(int, input().split())
    a_list = []
    b_list = []
    for _ in range(n):
        a, b = map(int, input().split())
        a_list.append(a)
        b_list.append(b)

    a_list.sort()
    b_list.sort()

    if n % 2 == 1:
        print(b_list[(n - 1) // 2] - a_list[(n - 1) // 2] + 1)
    else:
        lower = [a_list[n // 2 - 1], b_list[n // 2 - 1]]
        upper = [a_list[n // 2], b_list[n // 2]]

        ans = set()
        # for i in range(lower[0], lower[1] + 1):
        #     for j in range(max(upper[0], i), upper[1] + 1):
        #         ans.add((i + j) / 2)

        print(max(upper + lower) - min(upper + lower) + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 2
2 3"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
100 100
10 10000
1 1000000000"""
        output = """9991"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
read = sys.stdin.read


n = int(input())
ab = np.array(read().split(), dtype=np.int64).reshape([n,2]).T
a = ab[0]
b = ab[1]
if n%2 ==1:
    a.sort()
    b.sort()
    N = n//2+1
    ans = b[-N]-a[N]+1
else:
    a.sort()
    b.sort()
    N = n//2
    ans= (b[-N]-a[N])*2+1
print(ans)

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x:x[0])
A = sorted(A, key=lambda x:x[1])
# print(A)
n = 1
if N%2 == 1:
    a, b = A[(N-1)//2]
    print(b-a+1)
else:
    a1, b1 = A[N//2]
    a2, b2 = A[N//2-1]
    if (b1-a1)%2 == 0 or (b2-a2)%2 == 0:
        n += 1
    print(b1-a1+b2-a2+n)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

amax=0
bmin=10**100
arra=[]
arrb=[]
for i in range(n):
    a,b=mii()
    arra.append(a)
    arrb.append(b)

arra.sort()
arrb.sort()

if n%2==1:
    p=arra[n//2 +1]
    q=arrb[n//2 +1]

    print(q-p+1)
else:
    p=(arra[n//2 -1]+arra[n//2])/2
    q=(arrb[n//2 -1]+arra[n//2])/2
    print(q-p+1)

Submission status: Wrong Answer

Solution code:
import sys

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

n = N // 2 if N % 2 != 0 else N // 2 - 1
left = AB[n][0]

AB.sort(key=lambda x: x[1])
right = AB[n][1]

print(max(0, right - left + 1))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections
import bisect
from decimal import *


N = int(input())
A = []
B = []
for i in range(N):
    tmpA, tmpB = map(int, input().split())
    A.append(tmpA)
    B.append(tmpB)


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

Submission status: Wrong Answer

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

ans = 0
if n % 2 == 0:
    A = X[n // 2 - 1][1]
    B = X[n // 2][0]
    a = X[n // 2 - 1][1] - X[n // 2 - 1][0] + 1
    b = X[n // 2][1] - X[n // 2][0] + 1
    if B <= A:
        ans += (A - B + 1) * a -(A-B+1)
        b -= A - B + 1
    
    ans += a * b
else:
    ans = X[(n + 1) // 2 - 1][1] - X[(n + 1) // 2 - 1][0] + 1
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

AB = []

for n in range(N):
  AB.append(list(map(int, input().split())))

index = [AB[i][0] for i in range(len(AB))]
index = np.argsort(index)
AB = list(np.array(AB)[index])

if len(AB)%2==0:
  A = AB[len(AB)//2-1]
  B = AB[len(AB)//2]
  middle = max(B) - min(A)
  print(middle+1)
else:
  C = AB[len(AB)//2]
  print(C[-1]-C[0])

Submission status: Wrong Answer

Solution code:
import math


def median(array):
    if N % 2:
        return array[N // 2]
    else:
        return sum(array[N // 2 - 1: N // 2 + 1]) / 2


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

Submission status: Wrong Answer

Solution code:
n = int(input())

ab = [list(map(int, input().split())) for _ in range(n)]
ab = sorted(ab, key=lambda x:int(x[1]))

c = [ab[i][1]-ab[i][0] for i in range(n)]

if n%2 == 1:
    center = n//2
    answer = ab[center][1]-ab[center][0]
else:
    center = [n//2-1,n//2]
    answer1 = ab[center[0]][1] - ab[center[0]][0]+1
    answer2 = ab[center[1]][1] - ab[center[1]][0]+1
    answer = answer1*answer2 - max(0,ab[center[0]][1]-min(ab[center[0]][0],ab[center[1]][1]))

print(answer)

Submission status: Wrong Answer

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

AB.sort()
ab=AB[:]
ab.sort(key=lambda x:x[1])

if n%2==0:
    left=AB[n//2-1][0]
    right=ab[n//2][1]
    cnt=0
    cnt2=0
    
    nl=AB[0][0]
    nr=AB[0][1]
    for i in range(1,n):
        now=AB[i]
        if now[0]<=nr:
            nr=max(nr,now[1])
            #print(cnt,cnt2)
            cnt2+=cnt*(min(nr,right)-max(now[0],left))-((min(nr,right)-max(now[0],left))*(min(nr,right)-max(now[0],left)-1))//2
            #print(cnt,cnt2)
        else:
            #print(cnt,cnt2)
            cnt2+=cnt*(min(nr,right)-max(now[0],left))-((min(nr,right)-max(now[0],left))*(min(nr,right)-max(now[0],left)-1))//2
            #print(cnt,cnt2)
            cnt+=max(min(nr,right)-max(nl,left)+1,0)
            #print(cnt,cnt2)
            nl=now[0]
            nr=now[1]
    #print(cnt,cnt2)
    cnt2+=cnt*(min(nr,right)-max(now[0],left))-((min(nr,right)-max(now[0],left))*(min(nr,right)-max(now[0],left)-1))//2
    #print(cnt,cnt2)
    cnt+=max(min(nr,right)-max(nl,left)+1,0)
    #print(cnt,cnt2)
    print(cnt2)


else:
    left=AB[n//2][0]
    right=ab[n//2][1]
    cnt=0
    
    nl=AB[0][0]
    nr=AB[0][1]
    for i in range(1,n):
        now=AB[i]
        if now[0]<=nr:
            nr=max(nr,now[1])
        else:
            cnt+=max(min(nr,right)-max(nl,left)+1,0)
            nl=now[0]
            nr=now[1]
    cnt+=max(min(nr,right)-max(nl,left)+1,0)
    print(cnt)

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( ( B[ i2 ] - A[ i2 ] + 1 ) * ( B[ i1 ] - A[ i1 ] + 1 ) - 1 )
else:
  i = ( n + 1 ) // 2 - 1
  print( B[ i ] - A[ i ] + 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]
    if b2 - a2 == b1-a1:
        print(2 * (b1 - a1 + 1) - 1)
    else:
        print(max(b2-a2+1, b1-a1+1))
else:
    print(ran[N // 2])

Submission status: Wrong Answer

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

# A.sort()
# B.sort()
if N%2 == 1:
    X.sort(key=lambda x: x[0])
    min_range = [X[N//2][0], X[N//2+1][1]]
    
    X.sort(key=lambda x: x[1])
    max_range = [X[N//2-1][0], X[N//2][1]]
    diff = 0
    if min_range[1] >= max_range[0]:
        diff = min_range[1] - max_range[0] +1
    print(min_range[1]-min_range[0] +max_range[1]-max_range[0] -diff +2)
else:
    if N == 2:
        X.sort(key=lambda x: x[0])
        min_m = (X[N//2-1][0] +X[N//2][0])/2
        X.sort(key=lambda x: x[1])
        max_m = (X[N//2-1][1] +X[N//2][1])/2
        print(int((max_m -min_m)//0.5 +1))
#     m_min = (A[N//2-1] +A[N//2])/2
#     m_max = (B[N//2-1] +B[N//2])/2

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
y = sorted(x)
z = sorted(x, key=lambda x: x[1])

if n % 2 == 1:
    print(z[n//2][1] - y[n//2][0] + 1)
else:
    a = y[n//2-1][0]
    b = y[n//2][1]
    c = z[n//2-1][0]
    d = z[n//2][1]
    e = (b + d) / 2
    f = (a + c) / 2
    print(int((e - f) * 2) + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    event = []
    for _ in range(n):
        a, b = map(int, input().split())
        event.append((a, 1))
        event.append((b + 1, 0))
    event.sort()

    if n % 2 == 1:
        left = right = 0
        for v, q in event:
            if q == 1:
                left += 1
                if left == (n + 1) // 2:
                    L = v
            else:
                right += 1
                if right == (n + 1) // 2:
                    R = v
        print(R - L)

    else:
        left = right = 0
        for v, q in event:
            if q == 1:
                left += 1
                if left == n // 2:
                    L = v
            else:
                right += 1
                if right == n // 2 + 1:
                    R = v
        print(R - L)

resolve()

Submission status: Wrong Answer

Solution code:
import statistics
import math
N = int(input())

n =[]
m =[]

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

nmean = statistics.median(n)
mmean =statistics.median(m)

if N%2 == 1:
    print(mmean - nmean + 1)
else:
    print(int(mmean - nmean)*2 +1 )

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [[int(i) for i in input().split()] for _ in range(n)]
x.sort(key=lambda x:x[0])
y = sorted(x,key=lambda x:x[1],reverse=True)
if n%2 == 1:
    c = n//2
    if x[c][1] >= y[c][0]:
        ans = y[c][1] - x[c][0] + 1
    else:
        ans = x[c][1] - x[c][0] + y[c][1] - y[c][0] + 2
    print(ans)
else:
    cl = n//2-1
    cr = n//2-1
    lr = x[cl][1]
    rl = y[cr][0]
    for i in range(n):
        if x[i][0] <= x[cl][0] <= x[i][1]:
            lr = max(lr,x[i][1])
        if x[i][0] <= x[cr][1] <= x[i][1]:
            rl = min(rl, x[i][0])
    if rl > lr:
        ans = (lr - x[cl][0] + 1)*(y[cr][1]-rl+1)
    else:
        ans = (y[cr][1]-x[cl][0]+1)*(y[cr][1]-x[cl][0])//2
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[]
C=[]
for _ in range(n):
    a,b = map(int,input().split())
    #AB.append((a,b))
    C.append(a)
    C.append(b)
C.sort()
#AB = sorted(AB,key=lambda x: x[1])
med = n//2

if n%2 != 0:
    p,q=C[2*n-n//2-1],C[n//2]
    print(p-q+1)
else:
    p,q,r,s = C[n//2-1],C[n//2],C[2*n-n//2-1],C[2*n-n//2]
    print(int(((s+r)/2 - (p+q)/2)*2 + 1))

Submission status: Wrong Answer

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

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(reverse=True)

mia = a[n//2]
mab = b[n//2]

if n%2==0:
    print((mab-mia+1)*2+1)
else:
    print(mab-mia+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)
    from statistics import median
    import math
    if n % 2 == 1:
        i = median(a)
        j = median(b)
        print(j - i + 1)
    else:
        i = int(median(a))
        j = math.ceil(median(b))
        print((j - i) * 2)
main()