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
input = sys.stdin.readline
from collections import *

def f(ma, mb):
    if ma==mb:
        return 1
        
    m = N//2
    mad = int(ma)
    mau = mad+1
    mbd = int(mb)
    mbu = mbd+1
    
    if str(ma)[-1]=='5' and str(mb)[-1]=='5':
        return mbu-mad+1
    elif str(ma)[-1]=='5':
        return mbd-mad+1
    elif str(mb)[-1]=='5':
        return mbu-mad+1
    else:
        return mbd-mad+1

N = int(input())
A, B = [], []

for _ in range(N):
    Ai, Bi = map(int, input().split())
    A.append(Ai)
    B.append(Bi)

A.sort()
B.sort()

if N%2==1:
    ma = A[N//2]
    mb = B[N//2]
    print(mb-ma+1)
else:
    m = N//2
    ma = (A[m-1]+A[m])/2
    mb = (B[m-1]+B[m])/2
    ans = f(ma, mb)
    print(ans)

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
            print(l,r)
        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+1:
                r1 = E
            if end >= n//2+2:
                r2 = E
                flag = 1
                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())
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[(N+1)//2-1]-A[(N+1)//2-1]+1)
else:
    B_min = B[N//2-1]
    A_min = A[N//2-1]
    A_max = A[N//2]
    B_max = B[N//2]
    print(A_max+B_max-A_min-B_min+1)

Submission status: Wrong Answer

Solution code:
arr = []
a,b = [],[]
for _ in range(int(input())):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
    arr.append([x,y])
arr.sort()
n = len(arr)
if n%2!=0:
    x = n//2
    print(arr[x][1]-arr[x][0]+1)
else:
    x = n//2
    y = x-1
    minn = (arr[x][0]+arr[y][0])/2
    maxx = (arr[x][1]+arr[y][1])/2
    print(minn,maxx)
    ans = (maxx-minn)/0.5
    print(int(ans)+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

LINE = defaultdict(lambda: [0, 0])
for a, b in AB:
    LINE[a][0] += 1
    LINE[b + 1][1] += 1

LINE = list(LINE.items())
LINE.sort()

ans = 0

small = 0
small_able = 0
prevx = -1


if N % 2 == 1:

    mn = 10 ** 10
    mx = 0

    flg = False

    for x, p in LINE:
        small_able += p[0]
        small += p[1]

        if (small_able - small) >= ((N + 1) // 2):
            flg = True
            mn = min(mn, x)

        if flg and not (small_able - small) >= ((N + 1) // 2):
            mx = max(mx, x - 1)
            flg = False

else:
    mn_0 = 10 ** 10
    mn_1 = 10 ** 10
    mx_0 = 0
    mx_1 = 0

    flg_0 = False
    flg_1 = False

    for x, p in LINE:
        small_able += p[0]
        small += p[1]

        # N // 2
        if (small_able - small) >= ((N) // 2):
            flg_0 = True
            mn_0 = min(mn_0, x)

        if flg_0 and not (small_able - small) >= ((N) // 2):
            mx_0 = max(mx_0, x - 1)
            flg_0 = False

        # N // 2 + 1
        if (small_able - small) >= ((N // 2) + 1):
            flg_1 = True
            mn_1 = min(mn_1, x)

        if flg_1 and not (small_able - small) >= ((N // 2) + 1):
            mx_1 = max(mx_1, x - 1)
            flg_1 = False

    mn = mn_0 + mn_1
    mx = mx_0 + mx_1


print(mx - mn + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
List = []

A = []
B = []

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

if N%2 == 1:
  A.sort()
  B.sort()
  ans = B[N//2] - A[N//2] + 1
  print(int(ans))
else:
  A.sort()
  B.sort()
  c = B[N//2] - A[N//2] + 1
  d = B[N//2-1] - A[N//2-1] + 1
  print(int(c+d-min(c,d)+1))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

if n % 2 == 1:
    mid = int(n/2)+1
    print(l[mid-1][-1]-l[mid-1][0]+1)

else:
    mid_l = int(n/2)
    mid_r = int(n/2)+1
    
    print(l[mid_r-1][-1]-l[mid_l-1][0]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
num = []


for i in range(n):
    a, b = map(int, input().split())
    num.append((a, b))
l = 0
r = 10**9+1
while r - l > 1:
    m = l + (r-l)//2
    count = 0
    for i in range(n):
        if num[i][1] >= m:
            count += 1

    if count >= (n+1)//2:
        l = m
    else:
        r = m

right = l


l = -1
r = 10**9+1
while r - l > 1:
    m = l + (r-l)//2
    count = 0
    for i in range(n):
        if m >= num[i][0]:
            count += 1

    if count >= (n+1)//2:
        r = m
    else:
        l = m
left = r
if n % 2 == 1:

    print(right-left+1)
else:
    print((right-left)*2-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


if __name__ == '__main__':
    n = int(input())
    a_s = [0] * n
    b_s = [0] * n
    for i in range(n):
        a, b = list(map(int, input().split()))
        a_s[i] = a
        b_s[i] = b
    a_s.sort()
    b_s.sort()
    #print('a_s') # debug
    #print(a_s) # debug
    #print('b_s') # debug
    #print(b_s) # debug
    if n % 2 == 0:
        mb2 = (b_s[n // 2] + b_s[n // 2])
        ma2 = (a_s[n // 2] + a_s[n // 2])
        ans = mb2 - ma2 + 1
    else:
        ans = b_s[n // 2] - a_s[n // 2] + 1
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
a.sort()
b.sort()
if n % 2 == 1:
    am = a[n // 2]
    bm = b[n // 2]
    ans = abs(bm - am) + 1
else:
    am1 = a[n // 2 - 1]
    am2 = a[n//2]
    bm1 = b[n // 2 - 1]
    bm2 = b[n // 2]
    ans = am2 + bm2 - (am1 + bm1) + 1
print(ans)

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]
    del info[n // 2 - 1]
    info = sorted(info)[::-1]
    rmin, r = info[n // 2 - 1]
    print((lmax - l + 1) + (r - rmin + 1) - 1)

Submission status: Wrong Answer

Solution code:
import statistics

n = int(input())

# cand = {}
# for i in range(n):
#     a, b = list(map(int, input().split()))
#     c = {e for e in range(a, b + 1)}


a_list = []
b_list = []

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

# print(a_list)
# print(b_list)

if n % 2 == 1:
    median_a = statistics.median(a_list)
    median_b = statistics.median(b_list)
    print(median_b - median_a + 1)
else:
    median_a = statistics.median_low(a_list)
    median_b = statistics.median_high(b_list)
    print(median_b - median_a + 1)


# print(a_list)
# print(b_list)

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
    r = 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:
            r+=1
            aNext+=1
        while bNext < len(B) and B[bNext]==c:
            r-=1
            bNext+=1
        S.append((c,r))
    if N%2 == 0:
        criteria = N // 2
        begin = 0
        end = 0
        seekBegin = True
        for s in S:
            if seekBegin:
                if s[1] >= criteria:
                    begin = s[0]
                    seekBegin = False
            else:
                if s[1] < criteria:
                    end = s[0]
                    break
        print(end - begin + 1)
    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[1] < 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 sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    L=sorted(L, key=lambda x: x[0])
    if N%2==0:
        M=(L[N//2][1]+L[N//2-1][1])/2
        m=(L[N//2][0]+L[N//2-1][0])/2
        print(int((M-m)//0.5+1))
    else:
        M=L[N//2][1]
        m=L[N//2][0]
        print(int(M-m+1))
    
    
    

    
resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

A = [a for a, _ in AB]
B = [b for _, b in AB]

A.sort()
B.sort()

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    nums = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a == b:
            nums.append(a)
        else:
            nums.append(a)
            nums.append(b)
    sn = list(sorted(nums))
    kukans = []
    old = sn[0]
    for si in sn[1:]:
        kukans.append(si-old+1)
        old = si
    size = len(kukans)
    # if size%2:
    #     middle1 = kukans[size//2]
    #     middle2 = kukans[size//2+1]
        
    middle1 = kukans[size//2-1]
    middle2 = kukans[size//2]
    if n%2:
        print(middle1+middle2-1)
    else:
        print(middle1+middle2-1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
if n%2 == 1:
  for ab in abl:
    al.append(ab[0])
    bl.append(ab[1])
    if len(al) > 2:
      al.remove(max(al))
      al.remove(min(al))
      bl.remove(max(bl))
      bl.remove(min(bl))
  print(bl[0]-al[0]+1)
else:
  for ab in abl:
    al.append(ab[0])
    bl.append(ab[1])
    if len(al) > 3:
      al.remove(max(al))
      al.remove(min(al))
      bl.remove(max(bl))
      bl.remove(min(bl))
  ax2 = al[0]+al[1]
  bx2 = bl[0]+bl[1]
  print(bx2-ax2+1)

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N = int(input())
AB = []
for _ in range(N):
    AB.append(list(map(int, input().split())))
if N % 2 == 1:
    idx = N // 2
    ans = AB[idx][1] - AB[idx][0] + 1
else:
    idx1 = (N-1) // 2
    idx2 = (N-1) //2 + 1
    a1 = set({i for i in range(AB[idx1][0], AB[idx1][1]+1)})
    a2 = set({i for i in range(AB[idx2][0], AB[idx2][1]+1)})
    sum_a = set(a1 | a2)
    ans = cmb(len(sum_a), 2)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if N%2==1:
    flat=[j for i in A for j in i]
    flat=sorted(flat)
    if flat[-2]==flat[1]:
        print(1)
    else:
        print(flat[-2]-flat[1]+1)
else:
    flat=[j for i in A for j in i]
    flat=sorted(flat)
    if flat[-2]==flat[1]:
        print(3)
    else:
        print((flat[-2]-flat[1])*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]
    if B1 < A2:
        print(B1-A1+1 + B2-A2+1)
    else:
        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 = []
min_list = []
max_list = []
for i in range(N):
    AB.append(list(map(int,input().split())))
    min_list.append(AB[i][0])
    max_list.append(AB[i][1])

if N % 2 != 0:
    print(max_list[N//2] - min_list[N//2] + 1)
else:
    max_center = (max_list[N//2-1] + max_list[N//2])/2
    min_center = (min_list[N//2-1] + min_list[N//2])/2
    print(max_center*2 - min_center*2 + 1)

Submission status: Wrong Answer

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

a = sorted([a for a, b in AB])
b = sorted([b for a, b in AB])

if N % 2 == 1:
    print(b[N // 2] - a[N // 2] + 1)
elif N % 2 == 0:
    print((b[(N + 1) // 2] + b[N // 2]) - (a[(N + 1) // 2] + a[N // 2]) + 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 == 1:
    mid = (n+1)//2-1
    res = b_list[mid] - a_list[mid] + 1
else:
    mid_f = n//2-1
    mid_s = n//2
    num_f = (b_list[mid_f]-a_list[mid_f]+1)
    num_s = (b_list[mid_s]-a_list[mid_s]+1)
    num_all = num_f*num_s
    res = num_all
    if a_list[mid_s] <= b_list[mid_f]:
        res -= b_list[mid_f] - a_list[mid_s] + 1
print(res)

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

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)

    if N % 2 == 1:
        mid = N // 2
        ans += BA[mid][BA_B_IDX] - BA[mid+1][BA_A_IDX]

        if BA[mid+1][BA_A_IDX] - BA[mid][BA_A_IDX] >= 0:
            ans += BA[mid+1][BA_A_IDX] - BA[mid][BA_A_IDX]

        print(ans + 1)
    else:
        mid = N // 2 - 1
        ans += BA[mid][BA_B_IDX] - BA[mid+1][BA_A_IDX]

        if BA[mid+1][BA_A_IDX] - BA[mid][BA_A_IDX] >= 0:
            ans += BA[mid+1][BA_A_IDX] - BA[mid][BA_A_IDX]

        print(ans + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X1 = sorted(X)
X2 = sorted(X, key=lambda x: - x[1])


if N % 2 == 1:
    LA, LB = -1, float('inf')
    for a, b in X1[:N // 2 + 1]:
        LA = max(LA, a)
        LB = min(LB, b)

    RA, RB = -1, float('inf')
    for a, b in X2[:N // 2 + 1]:
        RA = max(RA, a)
        RB = min(RB, b)

    print(min(LB, RB) - max(LA, RA) + 1)

else:
    LA, LB = -1, float('inf')
    for a, b in X1[:N // 2]:
        LA = max(LA, a)
        LB = min(LB, b)

    RA, RB = -1, float('inf')
    for a, b in X2[:N // 2]:
        RA = max(RA, a)
        RB = min(RB, b)

    M_MIN = (LA + RA) / 2
    M_MAX = (LB + RB) / 2
    print(int(((M_MAX - M_MIN - 0.5) * 2) + 2))

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

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    AB=LLIN(N)
    l = []
    r = []
    for a,b in AB:
        l.append(a)
        r.append(b)
    l.sort()
    r.sort(reverse = True)

    l_lim = l[(N-1)//2]
    r_lim = r[(N-1)//2]
    # print(l_lim, r_lim)
    if(N&1):
        print(r_lim - l_lim + 1)
    else:
        l_lim2 = l[(N-1)//2 + 1]
        r_lim2 = r[(N-1)//2 + 1]
        # print("lim2",l_lim2, r_lim2)
        ans = max(0,(r_lim2 - l_lim2) * 2 + 1)
        # print(ans)
        L_low = (l_lim + l_lim2)/2
        L_high = min(l_lim2, (l_lim2 + r_lim)/2)
        # print("L",L_low, L_high)
        ans += int((L_high - L_low) * 2)
        R_low = max(r_lim2,(r_lim2 + l_lim)/2)
        R_high = (r_lim + r_lim2)/2
        # print("R",R_low,R_high)
        ans += int((R_high - R_low) * 2)
        # print("A")
        print(ans)
    # ABL=sorted(AB, key=lambda x:x[1])
    # ABR=sorted(AB, key=lambda x:x[0],reverse = True)

    # left_lim = 0
    # for a,b in ABL[:(N-1)//2]:
    #     left_lim = max(left_lim, b)
    
    # right_lim = inf
    # for a,b in ABR[:(N-1)//2]:
    #     right_lim = min(a, right_lim)
    
    # print(left_lim, right_lim)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

for i in range(len(C)):
    for j in range(2):
        C[i][j] *= 2
# print(C)

l = 0
r = 10**10
m = (l+r)//2
while r-l > 1:
    c = 0
    d = 0
    for i in range(n):
        if C[i][1] < m:
            c += 1
        if C[i][1] > m:
            d += 1
    if c-d <= 0 or c-d < (n-c-d):
        l = m
    else:
        r = m
    # print(l,r,m,c,d)
    m = (l+r)//2
# print(l)
aa = l
# print("aa",aa)

l = 0
r = 10**10
m = (l+r)//2
while r-l > 1:
    c = 0
    d = 0
    for i in range(n):
        if C[i][0] > m:
            c += 1
        if C[i][0] < m:
            d += 1
    # print(l,r,m,c,d)
    if c-d <= 0 or c-d < (n-c-d):
        # print("OK")
        r = m
    else:
        l = m
        # print("NG")
    
    m = (l+r)//2
# print(r)
bb = r
# print("bb",bb)
ans = aa-bb+1
# print(ans)
if n%2 == 1:
    cc = (bb-1) // 2
    dd = aa // 2
    ans = dd - cc
    # print(dd,cc)
else:
    ans = aa - bb + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _i in range(n)]
x, y = [], []
for i, j in ab:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
p = n//2
if n%2==0:
    p -= 1
    result = (x[p+1]-x[p]+1)*(y[p+1]-y[p]+1)
else:
    result = x[p+1]-x[p]+y[p]-y[p-1]
    if x[p+1]==y[p-1]:
        result += 1
    else:
        result += 2
print(result)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n = int(input())
nums = set()
A = []
B = []
for i in range(n):
    a,b = map(int, input().split())
    nums.add(a)
    nums.add(b)
    A.append(a)
    B.append(b)
A.sort()
B.sort(reverse=True)
if n % 2 == 1:
    mn = A[(n+1)//2-1] 
    mx = B[(n+1)//2-1]
    print(mx - mn + 1)
else:
    mn1 = A[(n+1)//2-1]
    mn2 = A[(n+1)//2]    
    mx1 = B[(n+1)//2]    
    mx2 = B[(n+1)//2-1]
    print((mn2+mx2)-(mn1+mx1)+1)

Submission status: Wrong Answer

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = []
	b = []
	for i in range(n):
		ai, bi = map(int, sys.stdin.readline().split())
		a.append(ai)
		b.append(bi)
	a_sort = sorted(a)
	if n % 2 == 0:
		min_center = int((a_sort[int(n/2)-1] + a_sort[int(n/2)])/2)
	else:
		min_center = a_sort[int((n+1)/2)-1]
	b_sort = sorted(b)
	if n % 2 == 0:
		max_center = int((b_sort[int(n/2)-1] + b_sort[int(n/2)])/2)
	else:
		max_center = b_sort[int((n+1)/2)-1]
	log.print(max_center, min_center)
	if n % 2 == 0:
		print((max_center - min_center)*2 + 1)
	else:
		print(max_center - min_center + 1)


	
	


main()

Submission status: Wrong Answer

Solution code:
N = int(input())
left = []
right = []
for _ in range(N):
    A, B = list(map(int, input().split()))
    left.append(A)
    right.append(B)
left.sort()
right.sort(reverse=True)
n = (N+1)//2-1
print(right[n]-left[n]+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 == 1:
    mid = (n+1)//2-1
    res = b_list[mid] - a_list[mid] + 1
else:
    mid_f = n//2-1
    mid_s = n//2
    num_f = (b_list[mid_f]-a_list[mid_f]+1)
    num_s = (b_list[mid_s]-a_list[mid_s]+1)
    num_all = num_f*num_s
    res = num_all
    if a_list[mid_s] <= b_list[mid_f]:
        res -= a_list[mid_s] - b_list[mid_f] + 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    A.sort()
    B.sort()

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


if __name__ == "__main__":
    main()

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 = 0, 10**9+1
        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 = -1, 10**9
        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 = 0, 10**9+1
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_right(A, P)
            if idx >= (n-1)//2:
                R = P
            else:
                L = P
        lm = 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
        lM = L-1
        rm, rM = -1, -1
        L, R = 0, 10**9+1
        while L+1 < R:
            P = (L+R)//2
            idx = bisect_right(A, P)
            if idx >= (n)//2:
                R = P
            else:
                L = P
        rm = R+1
        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()