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:
from bisect import bisect_right, bisect_left
N = int(input())
l = -1
r = 10**10
als = [0]*N
bls = [0]*N
for i in range(N):
  a,b = map(int, input().split())
  als[i] = a
  bls[i] = b
if N%2==0:
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_right(als,s)
    if i>=N//2:
      r = s
    else:
      l = s
  A1 = r
  x = als.index(A1)
  B1 = als[x+1] if x+1<len(als) else A1 
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_right(bls,s)
    if i>=N//2:
      r = s
    else:
      l = s
  A2 = r
  x = bls.index(r)
  B2 = bls[x+1] if x+1<len(bls) else A2
  ans = B2+A2-A1-B1+1
  print(ans)
else:
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_left(als,s)
    if i>N//2:
      r = s
    else:
      l = s
  A = l
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_left(bls,s)
    j = N-i
    if j>N//2:
      l = s
    else:
      r = s
  B = l
  print(B-A+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
prob = []
for _ in range(n):
    l = list(map(int,input().split()))
    prob.append(l)
if n%2==1:
    d = (n+1)//2
    print(prob[d-1][1]-prob[d-1][0]+1)
else:
    d1 = n//2
    d2 = (n//2) + 1
    diff1 = (prob[d1-1][1]-prob[d1-1][0]+1)
    diff2 = (prob[d2-1][1]-prob[d2-1][0]+1)
    print(diff1+diff2-1)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())

l = []
r = []

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

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

if n%2 == 1:
    print(r[(n-1)//2]-l[(n-1)//2]+1)
else:
    print(2*(r[(n-2)//2]-l[(n-2)//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( (( B[ i2 ] + A[ i2 ] ) - ( B[ i1 ] + A[ i1 ] )) // 2 + 1 )
else:
  i = ( n + 1 ) // 2 - 1
  print( B[ i ] - A[ i ] + 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.sort()
B.sort()
from statistics import median
Am = median(A)
Bm = median(B)
if N%2==1:
    ans = Bm-Am+1
else:
    ans = int(Bm-Am)*2+1

Submission status: Wrong Answer

Solution code:
from sys import stdin
from decimal import Decimal
N = int(stdin.readline().rstrip())
A = []
B = []
for i in range(N):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
    
A.sort()
B.sort()
if N % 2 == 0:
    ans = 2 * sum(B) - 2 * sum(A)
    print(ans//2+1)
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import copy

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

Submission status: Wrong Answer

Solution code:
def solve(N, As, Bs):
    # print(N)
    # print(As)
    # print(Bs)
    As.sort()
    Bs.sort()
    ans = 0
    # N が奇数の場合
    if N % 2 == 1:
        x = (N + 1) // 2 - 1
        ans = Bs[x] - As[x] + 1
    # N が偶数の場合
    else:
        lowx = N // 2 - 1
        highx = N // 2
        ans = (As[highx] + Bs[highx]) - (As[lowx] + Bs[lowx]) + 1
    print(ans)
    pass


if __name__ == '__main__':
    N = int(input())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    solve(N, A, B)

Submission status: Wrong Answer

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
import heapq
intervals = []
for i in range(n):
    intervals.append(tuple(map(int, input().split())))

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

if n%2 == 1:
    mid, prev = intervals[((n+1)//2)-1], intervals[(n+1)//2 - 2]
    # print(mid, prev)

    nm = mid[1] - mid[0] + 1
    print(nm)
    # if prev[0] < mid[0]:
    #     print(nm)
    # else:
        # print(mid[1] - prev[0] + 1)

else:
    l, r = intervals[(n//2)-1], intervals[(n//2)]
    # print(l, r)
    nl = l[1] - l[0] + 1
    nr = r[1] - r[0] + 1
    if l[1] < r[0]:
        print(nl*nr)
    else:
        ol = l[1] - r[0] + 1
        print(nl*nr - ol*ol)




# print(intervals)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
m = 0
M = 0
if N % 2 == 1:
    for i in range(N):
        k = list(map(int,input().rstrip().split(" ")))
        A.append(k[0])
        B.append(k[1])
    A.sort()
    B.sort()
    print(B[(N + 1) // 2 - 1] - A[(N + 1) // 2 - 1] + 1)
if N % 2 == 0:
    for i in range(N):
        k = list(map(int,input().rstrip().split(" ")))
        A.append(k[0])
        B.append(k[1])
    A.sort()
    B.sort()
    print(B[(N + 2) // 2 - 1] - A[N // 2 - 1] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
import heapq
intervals = []
for i in range(n):
    intervals.append(tuple(map(int, input().split())))

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

if n%2 == 1:
    mid, prev = intervals[((n+1)//2)-1], intervals[(n+1)//2 - 2]
    # print(mid, prev)

    nm = mid[1] - mid[0] + 1
    print(nm)
    # if prev[0] < mid[0]:
    #     print(nm)
    # else:
        # print(mid[1] - prev[0] + 1)

else:
    l, r = intervals[(n//2)-1], intervals[(n//2)]
    print(l, r)
    nl = l[1] - l[0] + 1
    nr = r[1] - r[0] + 1
    if l[1] < r[0]:
        print(nl*nr)
    else:
        ol = l[1] - r[0] + 1
        print(nl*nr - ol*ol)




# print(intervals)

Submission status: Wrong Answer

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

# print(al,bl)
al.sort()
bl.sort()


if n%2 == 1:
    print(bl[n//2] - al[n//2] + 1)
else:
    print(bl[n//2] - al[n//2-1] + 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))

if N%2:
    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(n-n2)
else:
#    print((N+1)//2, C(11))
    n = bsearch(-1, 10**9, lambda x : C(x)<(N+2)//2)
    n2 = bsearch(-1, 10**9, lambda x : C2(x)>=(N+1)//2)+1
    n3 = bsearch(-1, 10**9, lambda x : C(x)<(N)//2)
    n4 = bsearch(-1, 10**9, lambda x : C2(x)>=(N+3)//2)+1
#    print(n, n2)
#    print(n3, n4)
    print((n-n2+1)*(n3-n4+1))
#print(C(100))


#print(n, n2)

Submission status: Wrong Answer

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

if n%2 == 1:
    m_min = sorted(a)[n//2]
    m_max = sorted(b)[n//2]
    ans = m_max - m_min + 1
if n%2 == 0:
    m_min1 = sorted(a)[n//2 - 1]
    m_min2 = sorted(a)[n//2]
    m_max1 = sorted(b)[n//2 - 1]
    m_max2 = sorted(b)[n//2]
    ans = int(((m_max1 + m_max2)//2 - (m_min1 + m_min2)//2)//0.5) + 1
    
print(ans)

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())
m = n-1
if n % 2 == 0:
  a_c = int((a[int(m/2)]+a[int(m/2)+1])/2)
  b_c = int((b[int(m/2)]+b[int(m/2)+1])/2)
  print(int((b_c-a_c)*2)+1)
else:
  a_c = a[int((m+1)/2)]
  b_c = b[int((m+1)/2)]
  print(b_c-a_c+1)

Submission status: Wrong Answer

Solution code:
def median_cal(data):
    num = len(data)
    data.sort()
    if num % 2 == 0:
        median1 = int(num / 2)
        median2 = int(num / 2 - 1)
        median = (data[median1] + data[median2]) / 2.0
        return median
    else:
        median = int((num + 1) / 2 - 1)
        median = data[median]
        return median

n=int(input())
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 == 0:
    print(median_cal(B)*2 - median_cal(A)*2 + 1)
else:
    print(median_cal(B) - median_cal(A) + 1)

Submission status: Wrong Answer

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

mi = 1
ma = 10 ** 9 + 1

for i in range(n):
    if ab[i][0] == ab[i][1]:
        continue
    elif ma == ab[i][0]:
        ma = ab[i][1]
    else:
        mi = max(mi,ab[i][0])
        ma = min(ma,ab[i][1])
print(ma-mi+1)

Submission status: Wrong Answer

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

A, B = sorted(AB[::2]), sorted(AB[1::2])

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

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 )

sorted( A )
sorted( B )

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
list_A, list_B = list(), list()
for _ in range(N):
    A, B = map(int, input().split())
    list_A.append(A)
    list_B.append(B)

list_A.sort()
list_B.sort()

if N%2==0:
    tmp, tmp1 = N//2-1, N//2
    _min = math.floor(max(list_A[tmp], list_A[tmp1]))
    _max = math.ceil(min(list_B[tmp], list_B[tmp1]))
else:
    tmp = N//2
    _min = math.floor(list_A[tmp])
    _max = math.ceil(list_B[tmp])

print(_max-_min+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
ma = []
mi = []
for i in range(N):
    x1, x2 = map(int, input().split())
    mi.append(x1)
    ma.append(x2)

L = 0
R = 0

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


print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq

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()
po = []
no = [0 for i in range(n)]
co = 0
ans = 0
pre = 0
pr = -1
if n % 2 != 0:
	for i in range(n):
		a,b = m()
		hq.heappush(po,[a,i])
		hq.heappush(po,[b,i])
	while len(po) != 0:
		kkk = hq.heappop(po)
		if co == (n // 2)+1:
			if pre != pr:
				ans += 1
			ans += kkk[0]-pre
			pr = kkk[0]
		if no[kkk[1]] == 0:
			no[kkk[1]] += 1
			co += 1
		else:
			no[kkk[1]] -= 1
			co -= 1
		pre = kkk[0]





else:
	for i in range(n):
		a,b = m()
		hq.heappush(po,[a,i])
		hq.heappush(po,[b,i])
	while len(po) != 0:
		kkk = hq.heappop(po)
		if co == (n // 2):
			if pre != pr:
				ans += 1
			ans += kkk[0]-pre
			pr = kkk[0]
		if no[kkk[1]] == 0:
			no[kkk[1]] += 1
			co += 1
		else:
			no[kkk[1]] -= 1
			co -= 1
		pre = kkk[0]


print(ans)

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:
input = raw_input

n = int(input())

pairs = []
kugiri = []
for i in range(n):
    pair = map(int, input().split(" "))
    a, b = pair
    pairs.append(pair)
    kugiri += [a-1, a, b, b+1]

kugiri = sorted(set(kugiri))
n_kugiri = len(kugiri)
nums = [0] * n_kugiri
for a, b in pairs:
    ai = kugiri.index(a)
    bi = kugiri.index(b)
    for j in range(ai, bi+1):
        nums[j] += 1

# odd
#print(kugiri)
#print(nums)
now_ok = False
out = 0
if n % 2 == 1:
    ok_num = (n+1) // 2 
    for i in range(n_kugiri):
        cur_val = kugiri[i]
        cur_num = nums[i]

        if cur_num >= ok_num:
            if now_ok:
                max_kugiri = cur_val
            else:
                now_ok = True
                min_kugiri = cur_val
                max_kugiri = cur_val
        else:
            if now_ok:
                now_ok = False
                out += max_kugiri - min_kugiri + 1
else:
    ok_num = 1 + (n // 2) 
    for i in range(n_kugiri):
        cur_val = kugiri[i]
        cur_num = nums[i]

        if cur_num >= ok_num:
            if now_ok:
                max_kugiri = cur_val
                max_i = i
            else:
                now_ok = True
                min_kugiri = cur_val
                max_kugiri = cur_val
                min_i = i
                max_i = i
        else:
            if now_ok:
                now_ok = False
                cur_out = max_kugiri - min_kugiri + 1
                cur_out += max_kugiri - min_kugiri

                if min_i-1 >= 0 and nums[min_i-1] >= ok_num - 1:
                    cur_out += 1
                if max_i+1 <= n_kugiri-1  and nums[max_i+1] >= ok_num - 1:
                    cur_out += 1

                out += cur_out

print(out)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l=[list(map(int,input().split())) for _ in range(N)]
l1=[]
l2=[]
for i in range(N):
    l1.append(l[i][0])
    l2.append(l[i][1])
l1.sort()
l2.sort()
if N%2==0:
    minmed=(l1[N//2]+l1[N//2-1])//2
    maxmed=(l2[N//2]+l2[N//2-1])//2
    print(2*(maxmed-minmed)+1)
else:
    minmed=l1[N//2]
    maxmed=l2[N//2]
    print(maxmed-minmed+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
if N%2==0:
    l=[]
    for a,b in zip(A,B):
        l.append((a,b))
    sa=list(sorted(l,key=lambda t:(t[0],t[1])))
    sb=list(sorted(l,key=lambda t:(t[1],t[0])))
    ll=sa[N//2-1][0]
    lr=sa[N//2-1][1]
    rl=sb[N//2][0]
    rr=sb[N//2][1]
    lr=min(lr,rr)
    rl=max(rl,ll)
    ans=0
    ans+=rr-rl+1
    ans+=lr-ll
    print(ans)
else:
    if N==1:
        print(B[0]-A[0]+1)
    else:
        u=list(set(A+B))
        u.sort()
        d={x:i for i,x in enumerate(u)}
        aa=[d[x] for x in A]
        bb=[d[x] for x in B]
        l=[]
        for a,b in zip(aa,bb):
            l.append((a,b))
        aa.sort()
        bb.sort()
        left=aa[N//2-1]
        right=bb[N//2+1]
        class RangeBIT:
            def __init__(self,n):
                self.p=self.BIT(n+1)
                self.q=self.BIT(n+1)
            
            def add(self,s,t,x):
                self.p.add(s,-x*s)
                self.p.add(t,x*t)
                self.q.add(s,x)
                self.q.add(t,-x)
            
            def sum(self,s,t):
                return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
            
            class BIT:
                def __init__(self,n):
                    self.num=n
                    self.dat=[0]*(self.num+1)
                
                def add(self,i,x):
                    i+=1
                    while i<=self.num:
                        self.dat[i]+=x
                        i+=i&-i
                
                def sum(self,i):
                    i+=1
                    s=0
                    while i>0:
                        s+=self.dat[i]
                        i-=i&-i
                    return s
        bit=RangeBIT(len(u))
        for a,b in l:
            if left==a:
                lleft=aa[N//2]
            else:
                lleft=left
            if right==b:
                rright=bb[N//2]
            else:
                rright=right
            a=max(lleft,a)
            b=min(rright,b)
            if a<=b:
                bit.add(a,b+1,1)
        ans=0
        tmp=-1
        for i in range(len(u)):
            if bit.sum(i,i+1):
                if tmp==-1:
                    tmp=i
            else:
                if tmp>=0:
                    ans+=u[i-1]-u[tmp]+1
                    tmp=-1
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline
n = int(rl())
a = []
b = []
for _ in range(n):
    aa, bb = map(int, rl().split())
    a.append(aa)
    b.append(bb)

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
a = heapsort(a)
b = heapsort(b)
if n&1:
    ans = b[n//2] - a[n//2] + 1
else:
    c = a[n//2] - a[n//2 - 1]
    d = b[n//2] - b[n//2 - 1]
    ans = (c/2 + d/2) / 0.5 + 1
print(ans)

Submission status: Wrong Answer

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

# print(al,bl)
al.sort()
bl.sort()


print(bl[n//2] - al[n//2] + 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(key=lambda x:(x[0],-x[1]))
ABs_desc.sort(key=lambda x: (-x[1],x[0]))

if N%2:
    A1,B1 = ABs[N//2]
    A2,B2 = ABs_desc[N//2]
    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:
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [AB[i][0] for i in range(n)]
B = [AB[i][1] for i in range(n)]
# A = [(AB[i][0], i) for i in range(n)]
# B = [(AB[i][1], i) for i in range(n)]

A.sort()
B.sort()

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0 
if n%2 == 1:
    for i in range(1,n+1):
        if i == (n+1)//2:
            a,b = map(int, input().split())
            ans = b-a+1 
        else:
            _ = input()

else:
    for i in range(1, n+1): 
        if i == n//2:
            a1, b1 = map(int, input().split())
        elif i == n//2 + 1:
            a2, b2 = map(int, input().split())
        else:
            _ = input()
    
    #print(a1, b1, a2, b2)
    ma = max(b1-a1+1, b2-a2+1)
    mi = min(b1-a1+1, b2-a2+1)
    ans = mi + ma - 1 

print(ans)

Submission status: Wrong Answer

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

def mid(AB, idx):
    if N % 2 == 0:
        return (AB[N//2-1][idx] + AB[N//2][idx]) / 2
    else:
        return AB[(N+1)//2-1][idx]

AB.sort()
amid = mid(AB, 0)
AB.sort(key=lambda x: x[1])
bmid = mid(AB, 1)
ans = 0
acnt, bcnt = 0, 0
cnt = 0
# amidとbmidの間に作ることのできる数値の個数をカウントする
for a, b in AB:
    ans += max(ans, min(bmid, b) - max(amid,a) + 1)
    if amid <= a <= b <= bmid:
        cnt += b - a + 1
    elif amid <= a <= bmid:
        cnt += bmid - a + 1
    elif amid <= b <= bmid:
        cnt += b - amid + 1
    elif a < amid and bmid < b:
        cnt = bmid - amid + 1 
        break
 
print(int(cnt))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n = int(input())
    A, B = [None]*n, [None]*n
    for i in range(n):
        A[i], B[i] = map(int, input().split())
    A.sort()
    B.sort()
    if n % 2 == 1:
        m, M = -1, -1
        L, R = -1, 10**9
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_right(A, P)
            if idx >= (n+1)//2:
                R = P
            else:
                L = P
        m = R
        L, R = 0, 10**9+1
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_left(B, P)
            if n-idx >= (n+1)//2:
                L = P
            else:
                R = P
        M = L
        print(max(0, M-m+1))
    else:
        lm, lM = -1, -1
        L, R = -1, 10**9
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_right(A, P)
            if idx >= n//2:
                R = P
            else:
                L = P
        lm = R
        L, R = 0, 10**9+1
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_left(B, P)
            if n-idx >= n//2+1:
                L = P
            else:
                R = P
        lM = L
        rm, rM = -1, -1
        L, R = -1, 10**9
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_right(A, P)
            if idx >= n//2+1:
                R = P
            else:
                L = P
        rm = R
        L, R = -1, 10**9
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_left(B, P)
            if n-idx >= n//2:
                L = P
            else:
                R = P
        rM = L
        print(max(0, (lM+rM)-(lm+rm)+1))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
low = []
up = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append([A, B])
    low.append(A)
    up.append(B)
    
low = sorted(low)
up = sorted(up)
    
if N%2 == 1:
    m_up = up[N//2]
    m_low = low[N//2]
    ans = m_up-m_low+1
    print(ans)
else:
    m_up = up[N//2]
    m_low = low[N//2-1]
    ans = (m_up-m_low)*2-1
    if low[N//2-1] == low[N//2]:
        ans += 1
    if up[N//2] == up[N//2-1]:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import statistics

n=int(input())
a = [[int(i) for i in input().split()] for j in range(n)]
min=[i[0] for i in a]
max=[i[1] for i in a]
if n%2==0:
    print(int(statistics.median(max)-statistics.median(min))*2+1)
else:
    print(int(statistics.median(max)-statistics.median(min))+1)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = []
    B = []
    for i in range(N):
        a, b = NMI()
        A.append(a)
        B.append(b)
    A.sort()
    B.sort()

    if N%2:
        l = A[(N+1)//2-1]
        r = B[(N+1)//2-1]
        print(r-l+1)
        exit()

    ll = A[N//2-1]
    lr = A[N//2]
    rl = B[N//2-1]
    rr = B[N//2]
    l = (ll+lr)/2
    r = (rl+rr)/2
    gap = r-l
    print(gap*2+1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


pool = []
for a,b in ab:
    af = sum([1 for a1,b1 in list(ab) if a1 <= a <= b1])
    bf = sum([1 for a1,b1 in list(ab) if a1 <= b <= b1])
    pool.append((a,af))
    pool.append((b, bf))

# print(pool)

max_pool = max([p[1] for p in pool])
pool = [p[0] for p in pool if p[1] >= max_pool-1]
# print(pool)

if max_pool%2 == 1:
    print(max(pool) - min(pool) + 1)
else:
    print(max(pool) - min(pool) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    x.append([int(each) for each in input().split()])

# print(x)
if n%2 == 1:
    line = x[(n-1)//2]
    print(line[1] - line[0] +1)
else:
    l1 = x[n//2-1]
    l2 = x[n//2]
    print((max(l1)+max(l2)) - (min(l1)+min(l2)) +1)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

p = []
for i in range(n):
    p.append(b[i] - a[i] + 1)
    #print(b[i] - a[i] + 1)

p.sort()
if n % 2 == 0:
    print(p[n//2] + 1)
else:
    print(p[n//2])

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
list_A, list_B = list(), list()
for _ in range(N):
    A, B = map(int, input().split())
    list_A.append(A)
    list_B.append(B)

list_A.sort()
list_B.sort()

if N%2==0:
    tmp, tmp1 = N//2-1, N//2
    _min = math.floor(min(list_A[tmp], list_A[tmp1]))
    _max = math.ceil(max(list_B[tmp], list_B[tmp1]))
else:
    tmp = N//2
    _min = math.floor(list_A[tmp])
    _max = math.ceil(list_B[tmp])

print(_max-_min+1)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math
from collections import Counter,defaultdict,deque
from heapq import heappop, heappush
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
def main():
    n = int(input())
    ab = []
    for _ in range(n):
        a,b = map(int,input().split())
        ab.append([a,b])
    ab.sort()
    que = []
    heapq.heapify(que)
    end = 0
    now = 0
    if n%2 == 1:
        l,r = 0,0
        flag = 0
        for i in range(n):
            left = ab[i][0]
            now += 1
            heappush(que,ab[i][1])
            while left > que[0]:
                E = heappop(que)
                end += 1
                now -= 1
                if now + end == n//2 + 1 and l == 0:
                    l = left
                if end == n//2 + 1:
                    r = E
                    flag = 1
                    break
            if flag:
                break
        while que and not flag:
            E = heappop(que)
            end += 1
            now -= 1
            if end >= n//2+1:
                r = E
                break
        print(r-l+1)
    if n%2 == 0:
        l1,l2,r1,r2 = 0,0,0,0
        flag = 0
        for i in range(n):
            left = ab[i][0]
            now += 1
            heappush(que,ab[i][1])
            while left > que[0]:
                E = heappop(que)
                end += 1
                now -= 1
                if now + end >= n//2 and l1 == 0:
                    l1 = left
                if now + end >= n//2+1 and l2 == 0:
                    l2 = left
                if end == n//2:
                    r1 = E
                if end == n//2+1:
                    r2 = E
                    flag = 1
                    break
                if flag:
                    break
        while que and not flag:
            E = heappop(que)
            end += 1
            now -= 1
            if end == n//2:
                r1 = E
            if end == n//2+1:
                r2 = E
                break
        print((r1+r2)-(l1+l2)+1)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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