Problem:


Score : 500 points

Problem Statement

There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i.
Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

Notes

The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.

If N is odd, the median is x_{(N+1)/2};

if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N

Output

Print the answer.

Sample Input 1

2
1 2
2 3

Sample Output 1

3

If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};

if X_1 = 1 and X_2 = 3, the median is 2;

if X_1 = 2 and X_2 = 2, the median is 2;

if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.

Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.

Sample Input 2

3
100 100
10 10000
1 1000000000

Sample Output 2

9991



Sample input:
2
1 2
2 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
AB = li2(N)
A = [0]*N
B = [0]*N
for i in range(N):
    A[i] = AB[i][0]
    B[i] = AB[i][1]

if N%2:
    num_a = sorted(A)[N//2]
    num_b = sorted(B)[N//2]
    print(num_b-num_a+1)
else:
    A = sorted(A)
    B = sorted(B)
    min_a = A[N//2-1]
    #max_a = B[N//2]
    #min_b = A[N//2-1]
    max_b = B[N//2]
    #print(max(max_b, )-min(min_a, min_b)+1)
    print(max_b-min_a+1)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

min = []
max = []

for i in range(N):
    A,B = list(map(int, input().split()))
    min.append(A)
    max.append(B)

min = sorted(min)
max = sorted(max)

if N % 2 == 0:
    min_m = min[N // 2]
    max_m = max[N // 2]
    ans = (max_m - min_m) * 2 + 1
else:
    min_m = min[N // 2]
    max_m = max[N // 2]
    ans = max_m - min_m + 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
    print(B2-A1+1)
else:
    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
    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:
# Count median
N=int(input())
m=[]
M=[]
for i in range(N):
    x,y=map(int,input().split())
    m.append(x)
    M.append(y)
m.sort()
M.sort(reverse=True)
if N%2!=0:
    mini=m[N//2]
    maxi=M[-N//2]
    print(maxi-mini+1)
else:
    mini=m[N//2-1]
    maxi=M[-N//2]
    print((maxi-mini)*2+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis1=[];lis2=[]
for i in range(n):
    a,b=MI()
    lis1.append(a)
    lis2.append(b)
lis1.sort()
lis2.sort()
if n%2==1:
    ans=max(0,lis2[(n-1)//2]-lis1[(n-1)//2]+1)
else:
    sup1=lis2[n//2-1]
    sup2=lis2[n//2]
    low1=lis1[n//2-1]
    low2=lis1[n//2]
    ans=2*(sup2-low1)-1
    if sup1==sup2:
        ans+=1
    if low1==low2:
        ans+=1
print(ans)

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-1))//2 if ol!= 1 else 1))




# print(intervals)

Submission status: Wrong Answer

Solution code:

import sys
read = sys.stdin.buffer.read
N, *AB = map(int, read().split())
AB,BA=list(zip(AB[::2],AB[1::2])),list(zip(AB[1::2],AB[::2]))

AB.sort()
BA.sort(reverse=True)

#print(AB)
#print(BA)

pos=(N-1)//2
ll=AB[pos][0]
lr=0
for a,b in AB[:pos+1]:
    lr=max(lr,b)
rr=BA[pos][0]
rl=rr
for b,a in BA[:pos+1]:
    rl=min(rl,a)

if N%2==1:
    l=max(ll,rl)
    r=min(rr,lr)
    print(r-l+1)
else:
    a1,b1=AB[pos]
    b2,a2=BA[pos]
    if a1==a2 and b1==b2:
        na,_=AB[pos+1]
        nb,_=BA[pos+1]
        l=ll+na
        r=rr+nb
        print(r-l+1)
    else:
        l=ll+rl
        r=rr+lr
        print(r-l+1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    generator = (map(int, readline().strip().split()) for _ in range(N))

    As = [0] * N
    Bs = [0] * N

    i = 0
    for a, b in generator:
        As[i] = a
        Bs[i] = b
        i += 1

    As.sort()
    Bs.sort(reverse=True)

    if N & 1:
        center = N // 2
    else:
        center = (N-1) // 2

    ac = As[center]
    bc = Bs[center]
    p = bc - ac + 1
    return p


def main():
    print(solve())


if __name__ == "__main__":
    main()

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[0] == ABs_desc[N//2][0]:
            A2,B2 = AB[0],AB[1]
            break
    print(B2-A1+1)
else:
    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[0] == ABs_desc[N//2][0]:
            A2,B2 = AB[0],AB[1]
            break
    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:
import statistics
n=int(input())
r=set([])
x=[[]]*n
for i in range(n):
  a,b=list(map(int,input().split()))
  x[i]=[a,b]
r0=statistics.median([x[z][0] for z in range(n)])
r1=statistics.median([x[z][1] for z in range(n)])
if ((r0*2) % 2)>0 or ((r1*2) % 2)>0:
  mult=2
else:
  mult=1
mult=int((r1-r0)*mult+1)
print(mult)

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)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
A = []
B = []
for i in range(n):
    a,b = ma()
    A.append(a)
    B.append(b)
A.sort()
B.sort(reverse=True)
if n%2==1:
    mi = A[n//2]
    ma = B[n//2]
    print(ma-mi+1)
else:
    mi1 = A[(n-1)//2]
    ma1 = B[(n-1)//2]
    mi2 = A[n//2]
    ma2 = B[n//2]
    d1 = ma1-mi1 +1
    d2 = ma2-mi2 +1

    print(d1*d2)
#print(ma,mi,d)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
import bisect
setrecursionlimit(10 ** 7)

n = int(input())
li = []
a_li = []
b_li = []

for _ in range(n):
    a,b = map(int,stdin.readline().rstrip().split())
    li.append([a,b])
    a_li.append(a)
    b_li.append(b)

li.sort()

ma = 0
mi = 10**20

for i in range(n+1):
    liv = a_li[:i]+b_li[i:]
    liv.sort()
    if n%2 == 1:
        ma = max(ma,liv[n//2])
        mi = min(mi,liv[n//2])
    else:
        ma = max(ma,liv[n//2])
        mi = min(mi,liv[(n-1)//2])

print(ma-mi+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
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==0:
    half = int(n/2)
    first = (a_list[half]+a_list[half])/2
    last = (b_list[half]+b_list[half])/2
    print(int((last-first)/0.5)+1)
else:
    half = int((n+1)/2)
    print(b_list[half-1]-a_list[half-1]+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:
  Max = (max(A)+max(B))/2
  Min = (min(A)+min(B))/2
  print(int((Max-Min)*2+1))

else:
  A = sorted(A)
  B = sorted(B)
  num = int(n/2)
  A_c = A[num]
  B_c = B[num]
  print(abs(B_c - A_c)+1)

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 = (d/2 - c/2) / 0.5 + 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
if n %2 == 0:
    m = n //2 -1
    ans = y[m]-x[m] +1
    print(ans)
    exit()
else:
    m = n//2
    ans = y[m] - x[m] + 1
    print(ans)
    exit()

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)
q=sorted(a)
w=sorted(b)
w=list(reversed(w))
p=n//2
if n%2==1:
  e=q[p]
  r=w[p]
  t=r-e+1
else:
  e=q[p-1]
  r=w[p-1]
  t=r-e
  print(2*t-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())

alist,blist=[],[]
for _ in range(N):
  a,b=map(int,input().split())
  alist.append(a)
  blist.append(b)
alist.sort()
blist.sort()
#print(ablist,alist,blist)

if N%2==1:
  left=alist[N//2]
  right=blist[-N//2]
  #print(left,right)
  print(right-left+1)
else:
  left1=alist[N//2-1]
  left2=alist[N//2]
  right1=blist[-N//2+1]
  right2=blist[-N//2]
  #print(left,right)
  print(right1+right2-left1-left2+1)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]", B: "List[int]"):
    S = []
    A.sort()
    B.sort()
    minA = A[0]
    maxB = B[-1]
    aNext = 0
    bNext = 0
    c = 0
    b = 0
    e = 0
    while aNext < len(A) or bNext < len(B):
        c = 0
        if aNext < len(A) and bNext < len(B):
            c = min(A[aNext],B[bNext])
        elif aNext < len(A):
            c = A[aNext]
        else:
            c = B[bNext]
        while aNext < len(A) and A[aNext] == c:
            b+=1
            aNext+=1
        while bNext < len(B) and B[bNext]==c:
            e+=1
            bNext+=1
        S.append((c,b,e))
    if N%2 == 0:
        criteria = N // 2
        begin = 0
        end = 0
        seekBegin = True
        containBegin = False
        containEnd = False
        for s in S:
            if seekBegin:
                if s[1] >= criteria:
                    begin = s[0]
                    if s[1] >= criteria+1:
                        containBegin = True
                    seekBegin = False
            else:
                if s[2] > criteria:
                    if s[2] > criteria+1:
                        containEnd = True
                    end = s[0]
                    break
        f = 0
        if containBegin:
            f+=1
        if containEnd:
            f+=1
        # print(begin,end)
        # print(S)
        print((end - begin-1)*2+1+f)
    else:
        criteria = N//2+1
        begin = 0
        end = 0
        seekBegin = True
        for s in S:
            if seekBegin:
                if s[1] >=criteria:
                    begin = s[0]
                    seekBegin = False
            else:
                if s[2] >= criteria:
                    end = s[0]
                    break
        print(end - begin+1)
    # print(S)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import statistics

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


left = []
right = []

for i in range(N):
    left.append(P[i][0])
    right.append(P[i][1])

lmed = statistics.median(left)
rmed = statistics.median(right)

if N % 2 == 0:
    print(int(rmed - lmed) * 2 + 1)
else:
    print(rmed - lmed+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]
    A1 = (A11+A12) / 2
    B1 = (A11+B12) / 2
    A21,B21 = sortB[mid]
    A22,B22 = sortB[mid]
    A2 = (A21+A22) / 2
    B2 = (A21+B22) / 2
    ans = min(B1, B2) - max(A1, A2) + 1
    if ans % 1 != 0:
        ans = int(ans*2)
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(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])

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]
    print(b1-a1+b2-a2+1)

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]
    if left[1] > right[1]:
        ans += right[1]-left[0]
    else:
        ans += left[1]-left[0]
else:
    left = AB[N//2]
    AB.sort(reverse=True,key=lambda x:x[1])
    right = AB[N // 2]
    ans += left[1]+right[1] - (left[0]+right[0])
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.append(a)
    B.append(b)
    
if(N % 2 == 1):
    k = int( (N-1) / 2 )
    print(B[k] - A[k] + 1)
else:
    k = int( N / 2 ) - 1
    print( B[k+1] - A[k+1] + 1 + B[k] - A[k] )

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] - X[n // 2 - 1][0] + 1
    b = X[n // 2][1] - X[n // 2][0] + 1
    ans = a * b - 1
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_list = []
b_list = []
a_list.sort()
b_list.sort()
for _ in range(n):
    a, b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)


if n%2==0:
    half = int(n/2)
    first = (a_list[half]+a_list[half])/2
    last = (b_list[half]+b_list[half])/2
    print(int((last-first)/0.5)+1)
else:
    half = int((n+1)/2)
    print(b_list[half-1]-a_list[half-1]+1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
aa = []
bb = []
for _ in range(n):
    a, b = map(int, readline().split())
    aa.append(a)
    bb.append(b)
aa.sort()
bb.sort(reverse=True)
if n % 2 == 0:
    print(bb[0] - aa[0] + 1)
else:
    print(bb[1] - aa[1] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int,input().split()))for i in range(n)]
ab.sort(key = lambda x : x[0])
ans = 0
if n % 2 == 0:
    l = ab[n//2-1][0] + ab[n//2][0]
    ab.sort(key = lambda x : x[1])
    h = ab[n//2-1][1] + ab[n//2][1]
    if l%2 == 0:
        ans += 1
        l = (l+1)//2
    else:
        l = l//2
    if h%2 == 1:
        ans += 1
        h = (h-1)//2
    else:
        h = h // 2
    ans += h - l + 1
else:
    l = ab[n//2][0]
    ab.sort(key = lambda x : x[1])
    h = ab[n//2][1]
    ans += h - l + 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.append(a)
    B.append(b)

A.sort()
B.sort()

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

Submission status: Wrong Answer

Solution code:
from itertools import product

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

print(B[N // 2] - A[N // 2] + 1)

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:
    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
    print(math.ceil(right) - math.floor(left) + 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 math import *

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

A.sort(key=lambda x: (x[0], x[1]))
B.sort(key=lambda x: (x[0], x[1]))

l, r = 0, 0
if A[-1][0] <= B[0][0]:
    l, r = A[-1][0], B[0][0]
else:
    r, l = A[-1][0], B[0][0]

ans = r - l + 1

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

ans += ceil(l - mid_a)
ans += ceil(mid_b - r)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
L=[]
R=[]
for i in range(n):
    a,b=map(int,input().split())
    L.append([a,b])
    R.append([b,a])
L.sort()
R=list(reversed(sorted(R)))
if n%2!=0:
    print(R[n//2][0]-L[n//2][0]+1)
else:
    d1=L[n//2-1][0]+L[n//2][0]
    L1=L[n//2:]
    C=[]
    for l in L1:
        C.append(l[1])
    C.sort()
    d2=L[n//2-1][0]+C[0]
    d4=R[n//2-1][0]+R[n//2][0]
    C=[]
    R1=R[n//2:]
    for r in R1:
        C.append(r[1])
    C=list(reversed(sorted(C)))
    d3=R[n//2-1][0]+C[0]
    if d2<d3:
        print(d2-d1+1+d4-d3+1)
    else:
        print(d4-d1+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.sort()
B.sort()
if N % 2 == 1:
    id = (N+1)//2
    print(B[-id] - A[id-1] + 1)
else:
    id = N // 2
    print(B[-id] - A[id-1] + 1)

Submission status: Wrong Answer

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


if n%2==0:
    half = int(n/2)
    first = (a_list[half]+a_list[half])/2
    last = (b_list[half]+b_list[half])/2
    print(int((last-first)/0.5)+1)
else:
    half = int((n+1)/2)
    print(b_list[half-1]-a_list[half-1]+1)

Submission status: Wrong Answer

Solution code:
def resolve():
    n=int(input())
    a=[]
    b=[]
    for _ in range(n):
        x, y = map(int, input().split())
        a.append(x)
        b.append(y)
    a.sort()
    b.sort()
    ans=0
    if n%2==0:
        k=int(n/2)
        print(max(b[k],b[k-1])-min(a[k],a[k-1])+1)
    else:
        k=n//2
        print(b[k]-a[k]+1)
resolve()

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)
    if i>N//2:
      r = s
    else:
      l = s
  B = l
  print(B-A+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
AB = li2(N)
A = [0]*N
B = [0]*N
for i in range(N):
    A[i] = AB[i][0]
    B[i] = AB[i][1]

if N%2:
    num_a = sorted(A)[N//2]
    num_b = sorted(B)[N//2]
    print(num_b-num_a+1)
else:
    A = sorted(A)
    B = sorted(B)
    min_a = A[N//2-1]
    max_a = B[N//2]
    min_b = A[N//2-1]
    max_b = B[N//2-1]
    print(max(max_b, max_a)-min(min_a, min_b)+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)

m = int(((n * 2) - 2) / 2)

A.sort()
p = A[m - 1]
B.sort(reverse=True)
q = B[m-1]
# print(p, q)

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.sort()
B.sort()
l = A[1]
r = B[-2]
if n % 2:
    print(r - l + 1)
else:
    print((r - l + 1) * 2 + 1)

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[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]
    print(b1-a1+b2-a2+1)

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

Submission status: Wrong Answer

Solution code:
import statistics
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort()
if N % 2 == 1:
    print(arr[N//2][1]-arr[N//2][0]+1)
else:
    print(arr[N//2][1]-arr[(N//2)-1][0]+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()
    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]
        b1 = min(b1, l1[n // 2-1])
        a2,b2=l[n//2]
        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:
from operator import itemgetter, attrgetter
from collections import defaultdict
n = int(input())
l = defaultdict(int)
a = []
b = []
ll = []
print(l)
ans = 0
for i in range(n):
    ta,tb = map(int,input().split())
    ll.append([ta,tb,i])
    a.append(ta)
    b.append(tb)
A = sorted(ll, key=itemgetter(0))
B = sorted(ll, key=itemgetter(1))
a.sort()
b.sort()
if n%2==0:
    a,b,c=A[n//2-1]
    d,e,f = B[n//2-1+(n%2==0)]
    ans = e-a+1
else:
    a,b,c=A[n//2]
    d,e,f = B[n//2]
    ans = b-a+1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
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 n % 2 == 0:
    ans += int((b1+b2)/2 - (a1+a2)/2 + 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())
    

if n%2==1:
    a_m = a[n//2]
    b_m = b[n//2]
    ans=max(b_m-a_m+1,0)
    print(ans)
else:
    a_m = (a[n//2]+a[n//2-1])
    b_m = (b[n//2]+b[n//2-1])
    ans = max(b_m-a_m+1,0)
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
ab1 = sorted(ab, key=lambda x:x[0])
ab2 = sorted(ab, key=lambda x:-x[1])
if n%2==1:
    print(ab2[n//2][1]-ab1[n//2][0]+1)
else:
    rmax = 0
    lmin = 10**9
    for i in range(n//2):
        rmax = max(rmax, ab1[i][1])
        lmin = min(lmin, ab2[i][0])
    print(ab2[n//2-1][1]+rmax-ab1[n//2-1][0]-lmin+1)

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 = []
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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
aa = []
bb = []
for _ in range(n):
    a, b = map(int, readline().split())
    aa.append(a)
    bb.append(b)
aa.sort()
bb.sort(reverse=True)
if n == 2:
    print(bb[0] - aa[0] + 1)
else:
    print(bb[1] - aa[1] + 1)