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 heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    N = I()
    AB = [None] * N
    BA = [None] * N
    ans = 0
    BA_B_IDX = 0
    BA_A_IDX = 1
    AB_A_IDX = 0
    AB_B_IDX = 1

    for i in range(N):
        a, b = MI()
        AB[i] = (a, b, i)
        BA[i] = (b, a, i)

    BA = sorted(BA, reverse=True)
    AB = sorted(AB)

    if N % 2 == 1:
        mid = N // 2
        mx = BA[mid][BA_B_IDX]
        mn = AB[mid][AB_A_IDX]

        # print(mx, mn, mid, AB)

        mn2 = AB[mid][AB_A_IDX]
        mx2 = BA[mid][AB_B_IDX]

        # print(mx2, mn2, mid, AB)
        if mx2 > mx and mn2 > mx:
            ans = mx - mn + 1 + mx2 - mn2 + 1
            print(ans)
        elif mx > mx2 and mn > mx2:
            ans = mx - mn + 1 + mx2 - mn2 + 1
            print(ans)
        else:
            print(max(mx, mx2) - min(mn, mn2) + 1)
    else:
        mid = N // 2 - 1
        mx = BA[mid][BA_B_IDX]
        mn = AB[mid][AB_A_IDX]

        # print(mx, mn, mid, AB)

        mn2 = AB[mid][AB_A_IDX]
        mx2 = BA[mid][AB_B_IDX]

        # print(mx2, mn2, mid, AB)

        if mx2 > mx and mn2 > mx:
            ans = mx - mn + 1 + mx2 - mn2 + 1
            print(ans)
        elif mx > mx2 and mn > mx2:
            ans = mx - mn + 1 + mx2 - mn2 + 1
            print(ans)
        else:
            print(max(mx, mx2) - min(mn, mn2) + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

As.sort()
Bs.sort()
if N % 2 == 0:
    mins = (As[N//2] + As[N//2-1]) / 2.0
    maxs = (Bs[N//2] + Bs[N//2-1]) / 2.0
else:
    mins,maxs = As[N//2], Bs[N//2]

print(int(maxs-mins)+1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

A.sort()
B.sort()

if n % 2 == 1:
    avrA = A[n // 2]
    avrB = B[n // 2]

    print(avrB - avrA + 1)
else:
    avr_low_A = A[n // 2 - 1]
    avr_high_A = A[n // 2]
    avr_low_B = B[n // 2 - 1]
    avr_high_B = B[n // 2]

    x = avr_low_B - avr_low_A + 1
    y = avr_high_B - avr_high_A + 1
    sum = 0
    if x > y:
        x, y = y, x
    for i in range(2, x + 1):
        m = (y - x + 1) * x
        sum += x + y - m + 1

    print(sum)

Submission status: Wrong Answer

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

A=[]
B=[]
for i in range(N):
    A.append(List[i][0])
    B.append(List[i][1])

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

if N%2==1:
    ans=B[int((N-1)/2)]-A[int((N-1)/2)]
else:
    ans=(B[int(N/2)]+B[int(N/2)-1])/2-(A[int(N/2)]+A[int(N/2)-1])/2

print(ans)

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
    i = int(median(a))
    j = int(median(b))
    if n % 2 == 1:
        print(j - i + 1)
    else:
        print((j - i) * 2)
main()

Submission status: Wrong Answer

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

if n % 2 == 1:
    info = sorted(info)
    l = info[n // 2][0]
    info = sorted(info)[::-1]
    r = info[n // 2][1]
    print(r - l + 1)

else:
    info = sorted(info)
    l, lmax = info[n // 2 - 1]
    info = sorted(info)[::-1]
    rmin, r = info[n // 2 - 1]
    length = []
    for i in range(n):
        length.append(min(r, info[i][1]) - max(l, info[i][0]) + 1)
    print(length)
    length = sorted(length, reverse=True)
    print(length[0] + length[1] - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB += [(A, B)]
sortA = sorted(AB, key=lambda x: x[0])
sortB = sorted(AB, key=lambda x: x[1])
if N % 2 == 0:
    mid = N//2-1
    A11,B11 = sortA[mid]
    A12,B12 = sortA[mid+1]
    # print(A11, B11)
    # print(A12, B12)
    A1 = (A11+A12) / 2
    B1 = (B11+B12) / 2
    A21,B21 = sortB[mid]
    A22,B22 = sortB[mid+1]
    A2 = (A21+A22) / 2
    B2 = (B21+B22) / 2
    ans = (min(B1, B2) - max(A1, A2))*2
    # print(B1, B2, A1, A2, ans)
    if ans % 1 != 0:
        ans += 1
else:
    mid = (N+1)//2-1
    A1,B1 = sortA[mid]
    A2,B2 = sortB[mid]
    # print(A1, A1, B1, B2)
    ans = min(B1, B2) - max(A1, A2) + 1
print(int(ans))

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)
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-floor(mA))*2
    elif mA%1==mA and mB%1!=mB:
        ans=(ceil(mB)-mA)*2
    else:
        ans=int(mB-mA)*2+1
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:
    print(y, x)
    print(math.ceil(y) - math.floor(x) + 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
    i = int(median(a))
    j = math.ceil(median(b))
    if n % 2 == 1:
        print(j - i + 1)
    else:
        print((j - i) * 2-1)
main()

Submission status: Wrong Answer

Solution code:
n = int(input())

isEven = n % 2 == 0

min = 10**9
min2 = 10**9
min3 = 10**9
max = -1
max2 = -1
max3 = -1

values = []
candidate = []
for i in range(n):
    a, b = map(int ,input().split())

    if a < min:
        min3 = min2
        min2 = min
        min = a
    elif a < min2:
        min3 = min2
        min2 = a
    elif a < min3:
        min3 = a

    if b > max:
        max3 = max2
        max2 = max
        max = b
    elif b > max2:
        max3 = max2
        max2 = b
    elif b > max3:
        max3 = b


if not isEven:
    print(max2 - min2 + 1)
else:
    if n == 2:
        print(max - min + 1)
    else:
        newMin = min2 + min3
        newMax = max2 + max3
        print(newMax - newMin + 1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
n = int(input())
X = []
As = []
Bs = []
for i in range(n):
    A, B = list(map(int, input().split()))
    As.append(A)
    Bs.append(B)
As.sort()
Bs.sort()

if n % 2 == 1:
    m = (n-1) // 2
    print(Bs[m] - As[m] + 1)
else:
    b_m = n // 2 - 1
    a_m = b_m 
    min_mid =  (As[b_m] + As[a_m])
    max_mid =  Bs[b_m] + Bs[a_m]
    print(max_mid - min_mid + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [None]*N
B = [None]*N

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

if N%2==0:
  x=A[N//2-1]
  y=B[N//2]
else:
  x=A[N//2]
  y=B[N//2]
print(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[0]][1] - ab[center[0]][0]+1
    answer = answer1*answer2
    
print(answer)

Submission status: Wrong Answer

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

A_sorted = sorted(A)
B_sorted = sorted(B)

if N % 2 != 0:
    n = N // 2
    a = A_sorted[n]
    b = B_sorted[-(n+1)]
    print(b-a+1)
else:
    n = N // 2
    a1 = A_sorted[n-1]
    a2 = A_sorted[n]
    b1 = B_sorted[-n]
    b2 = B_sorted[-n-1]
    a = (a1 + a2) / 2
    b = (b1 + b2) / 2
    print(int((a-b)*2 + 1))

Submission status: Wrong Answer

Solution code:
input()
input()
input()
print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = sorted([list(map(int,input().split())) for i in range(n)])
ab_b = sorted(ab,key=lambda x:x[1])
if n==2:
    x1 = ab_b[-1][1]+ab[0][1]/2
    x2 = ab_b[-1][0]+ab[0][0]/2
    ans = int((x1-x2)*2)
elif n%2==1:
    ans = ab_b[-2][1]-ab[1][0]+1
else:
    x1 = ab_b[-2][1]+ab[1][1]/2
    x2 = ab_b[-2][0]+ab[1][0]/2
    ans = int((x1-x2)*2)
print(ans)

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)

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)
    else:
        start = (rangeStart1 + rangeStart2)
        end = (rangeEnd2 + rangeStart2)
        result = (end - start) + 1
        print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()
a, b = map(list, zip(*ab))
a.sort()
b.sort(reverse=True)
a1, b1 = a[n//2], b[n//2]
a2, b2 = a[n//2-1], b[n//2-1]
ans = b1 - a1 + 1 if b1 >= a1 else 0
if n % 2 == 0:
    ans += int((b1+b2)/2 - (a1+a2)/2)
    if (b1+b2)%2 or (a1+a2)%2: ans += 1

print(ans)

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((1, a))
        event.append((0, b))
    event.sort()

    if n % 2 == 1:
        left = right = 0
        for q, v 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 + 1)

    else:
        left = right = 0
        for q, v 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 + 1)

resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for _ in range(n):
    a,b = map(int,input().split())
    l.append(a)
    l.append(b)
l2 = sorted(list(set(l)))
length = len(l2)
if length == 1:
  print(l2[0])
  exit()
if length%2==0:
  print(l2[length//2]-l2[length//2-1]+1)
  exit()
print(l2[length//2 + 1] - l2[length//2 - 1] + 1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    Xmin = min(A)
    Xmax = max(B)
    median = {}
    # あるX(Xmin<X<Xmax)について
    # 1.自分単体で中央値
    for i in range(Xmin+1,Xmax):
        if i not in median.keys():
            median[i] = 1
        if i<=Xmax-2 and 2*i+1 not in median.keys():
            median[2*i+1] = 1
    # 2.隣と一緒に中央値を作る
    print(len(median))


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, ne = intervals[((n+1)//2)-1], intervals[(n+1)//2 - 2], intervals[((n+1)//2)]
    # print(mid, prev)

    nm = mid[1] - mid[0] + 1

    if ne[0] < mid[0] and prev[0] < mid[0]:
        nm += (mid[0] - max(ne[0], prev[0]))
    print(nm)

else:
    l, r = intervals[(n//2)-1], intervals[(n//2)]
    # print(l, r)
    d = set()
    for i in l:
        for j in r:
            d.add(i+j)

    print(len(d))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    at, bt = map(int, input().split())
    a.append(at)
    b.append(bt)
if(n % 2 == 1):
    a.sort()
    b.sort()
    min_med = a[(n-1)//2]
    max_med = b[(n-1)//2]
    result = max_med - min_med + 1
else:
    a.sort()
    b.sort()
    min_med = a[n//2]
    max_med = b[n//2]
    result = (max_med - min_med)*2 + 1
print(result)

Submission status: Wrong Answer

Solution code:
import math
import statistics

ms = set()
for i in range(2,3+1):
    for j in range(3,5+1):
        for k in range(4, 6+1):
            a = sorted([i,j,k])
            m = statistics.median(a) 
            ms.add(m)
print(ms)
print(len(ms))

"""
ms = set()
for i in range(1,2+1):
    for j in range(2,5+1):
        a = sorted([i,j])
        m = statistics.median(a) 
        ms.add(m)
print(ms)
print(len(ms))
"""

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

if n%2 == 0:
    # print(pool)
    pool = [p[0] for p in pool if p[1] >= max_pool-1]
    print(max(pool) - min(pool) + 1)
else:
    # print(pool)
    pool = [p[0] for p in pool if p[1] >= max_pool]
    print(max(pool) - min(pool) + 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], reverse=True)
right = AB[n][1]

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

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)
            #print(cnt,cnt2)
        else:
            #print(cnt,cnt2)
            cnt2+=cnt+min(nr,right)-max(now[0],left)+1
            #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)
    #print(cnt,cnt2)
    cnt+=max(min(nr,right)-max(nl,left)+1,0)
    #print(cnt,cnt2)
    print(cnt)


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:
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 +1)
else:
  print((maxi-mini)*2+1)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A = []
B = []
ans = 0

for i in range(N):
    AB = input().split()
    A.append(int(AB[0]))
    B.append(int(AB[1]))

if(N%2==0):
    if(N ==2):
        ans = (max(B)+min(B))-(max(A)+min(A))+1
    else:
        A.remove(min(A))
        A.remove(max(A))
        B.remove(max(B))
        B.remove(min(B))
        ans = (max(B)+min(B))-(max(A)+min(A))+1
else:
    A.remove(min(A))
    A.remove(max(A))
    B.remove(max(B))
    B.remove(min(B))
    ans = max(B)-min(A)+1

print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import sys
import math

N = int(sys.stdin.readline().strip())
ABlist = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    ABlist.append((a, b))

Asorted = sorted(ABlist)
Bsorted = sorted(ABlist, key=lambda x: x[1])
if N % 2 == 1:
    left = Asorted[(N-1)//2][0]
    right = Bsorted[(N-1)//2][1]
    # print(left, right)
    print(right - left + 1)
else:
    if N == 2:
        left = (Asorted[(N-1)//2][0] + Asorted[(N-1)//2 + 1][0]) / 2
        right = (Bsorted[(N-1)//2][1] + Bsorted[(N-1)//2 + 1][1]) / 2
    else:
        left = (Asorted[(N-1)//2][0] + Asorted[(N-1)//2 + 2][0]) / 2
        right = (Bsorted[(N-1)//2 - 1][1] + Bsorted[(N-1)//2 + 1][1]) / 2
    print(math.ceil(right) - math.floor(left) + 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()
amin = min(A)
amax = max(A)
bmin = min(B)
bmax = max(B)

if N % 2 == 0:
    ans = 2 * (bmin-amin) + 2 * (bmax-amax)
    print(ans//2+1)
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)

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:
    for AB in ABs:
        if AB[0] == ABs[N//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[N//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    if B1 < A2:
        print(B1-A1+1 + B2-A2+1)
    else:
        print(B2-A1+1)
else:
    for AB in ABs:
        if AB[0] == ABs[(N-1)//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[(N-1)//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    print(B1+B2-A1-A2+1)

Submission status: Wrong Answer

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

for i in range(N):
    Q.append(P[i][1])
    R.append(P[i][0])

Q.sort()
R.sort()

if N%2==1:
    print(int(int(Q[-2])-int(R[1]))+1)
else:
    print(int(((((int(Q[-1])-int(Q[-2]))/2)-((int(R[0])-int(R[1]))/2))*2)+1))

Submission status: Wrong Answer

Solution code:
import statistics

n = int(input())
alist = []
blist = []
for i in range(n):
    a,b = map(int,input().split())
    alist.append(a)
    blist.append(b)
minMed = statistics.median(alist)
maxMed = statistics.median(blist)

if n%2 == 1:
    print(maxMed-minMed+1)
else:
    if (minMed*2) % 2 == 0:
        if (maxMed*2) % 2== 0:
            diff = maxMed - minMed
            print(int(2*diff-1 + 2))
        else:
            print(int(2* (maxMed*2 - minMed*2) -1))
    else:
        if (maxMed*2)%2 == 0:
            print(int(2* (maxMed*2 - minMed*2) -1))
        else:
            diff = 2*maxMed - 2*minMed
            print(int(diff+1))

Submission status: Wrong Answer

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(Decimal, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7
from decimal import Decimal


def main():

    n=int(data())
    l=[]
    l1=[]
    for i in range(n):
        l.append(mdata())
        l1.append(l[-1][1])
    l.sort(key=lambda x:x[1],reverse=True)
    l.sort(key=lambda x:x[0])
    l1.sort()
    if n%2!=0:
        a,b=l[n//2]
        b=min(b,l1[n//2])
        cnt=b-a+1
        out(cnt)
    else:
        a1,b1=l[n//2-1]
        a2,b2=l[n//2]
        if a1==a2:
            b1,b2=b2,b1
        b1 = min(b1, l1[n // 2 - 1])
        b2 = min(b2, l1[n // 2])
        out(int(((b1+b2)/2-(a1+a2)/2)*2+1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

mins = [0] * n
maxs = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    mins[i] = a
    maxs[i] = b

mins = sorted(mins)
maxs = sorted(maxs)

if n % 2 != 0:
    print(maxs[((n+1)//2) - 1] - mins[((n+1)//2) - 1] + 1)
else:
    print(((maxs[n//2] - mins[(n//2) - 1] + 1) * (maxs[n//2] - mins[(n//2) - 1])) // 2)

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+1
        elif MIN>MAX:
            break
        else:
            ans+=(MAX-MIN)*2+1
            break
    print(int(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]

m=10**10
M=-1
r=0
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
    if a<=m:
        if a==m and b>r:
            r=b
            idm=i
        elif a==m:
            continue
        idm=i
        m=a
l=10**10
idM=-1
for i in range(N):
    a=A[i]
    b=B[i]
    if M<=b:
        if M==b and a<l:
            l=a
            idM=i
        elif M==b:
            continue
        idM=i
        M=b
#print("m:{},M:{}".format(m,M))
#print("idm:{},idM:{}".format(idm,idM))
G=[]
for i in range(N):
    a=A[i]
    b=B[i]
    G.append([a,b,i])

G.sort()
tmp=0
cnt=0
for i in range(N):
    num=G[i][2]
    if num==idm or num==idM:
        continue
    a=G[i][0]
    b=G[i][1]
    tmp=max(a,tmp)
    if tmp>=b:
        continue
    cnt+=b-tmp
    #print(a,b,tmp)
    tmp=b
cnt+=1

if N==2:
    #print("ON")
    tmp=0
    cnt=0
    for i in range(N):
        a=A[i]
        b=B[i]
        tmp=max(a,tmp)
        if tmp>=b:
            continue
        cnt+=b-tmp
        tmp=b
    cnt+=1
    ans=(cnt*(cnt-1))//2
    print(cnt)
    exit()


if N%2==1:
    print(cnt)
else:
    ans=(cnt*(cnt-1))//2
    print(ans)

Submission status: Wrong Answer

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

def main():
  n = int(input().strip())
  item_list = []
  for i in range(n):
    item = list(map(int, input().strip().split()))
    item_list.append(item)

  item_list.sort(key=lambda x: x[0])

  if len(item_list) % 2 == 1:
    index = len(item_list) // 2
    result = item_list[index][1] - item_list[index][0] + 1
  else:
    index1 = len(item_list)//2 -1
    index2 = index1 + 1
    result = item_list[index2][1] - item_list[index1][0] + 1

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

  if len(item_list) % 2 == 1:
    index = len(item_list) // 2
    tmp = item_list[index][1] - item_list[index][0] + 1
    print(max(result, tmp))
  else:
    index1 = len(item_list)//2 -1
    index2 = index1 + 1
    tmp = item_list[index2][1] - item_list[index1][0] + 1
    print(max(result, tmp))

main()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n)]

A = [a for a,b in ab]
A.sort()
B = [b for a,b in ab]
B.sort()
if n % 2:
    print(B[n//2] - A[n//2] + 1)
else:
    xa, xb = A[n//2 - 1], B[n//2-1]
    ya, yb = A[n//2], B[n//2]
    print(2*(yb - xa) - 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)

medians = []
for a in A:
    for b in B:
        n = (b - a) + 1
        if n % 2 == 0:
            indx = int(n/2)
            med = (a+indx-1+a+indx) / 2
        else:
            indx = int((n+1)/2)
            med = a + indx-1
        
        medians.append(med)

medians = set(medians)
print(len(medians))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort()
ans = 1
if N % 2:
    left = AB[N // 2]
    AB.sort(reverse=True,key=lambda x:x[1])
    right = AB[N // 2]
    ans += right[1]-left[0]

else:
    left = AB[N//2-1]
    AB.sort(reverse=True,key=lambda x:x[1])
    right = AB[N // 2-1]
    ans += left[1]+right[1] - (left[0]+right[0])

print(ans)