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 statistics import median
import numpy as np
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_arr = np.array(A_list)
B_arr = np.array(B_list)

sort_index = np.argsort(A_arr)
A = A_arr[sort_index]
B = B_arr[sort_index]

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import copy

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

Submission status: Wrong Answer

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
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 = BA[mid+1][BA_A_IDX]

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

        mn2 = AB[mid][AB_A_IDX]
        mx2 = AB[mid+1][AB_B_IDX]

        if AB[mid][AB_B_IDX] - AB[mid+1][AB_B_IDX] >= 0:
            mx2 = AB[mid][AB_B_IDX]

        print(max(mx, mx2) - min(mn, mn2) + 1)
        # print(mx2 - mn2 + 1)
    else:
        mid = N // 2 - 1
        mx = BA[mid][BA_B_IDX]
        mn = BA[mid+1][BA_A_IDX]

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

        mn2 = AB[mid][AB_A_IDX]
        mx2 = AB[mid+1][AB_B_IDX]

        if AB[mid][AB_B_IDX] - AB[mid+1][AB_B_IDX] >= 0:
            mx2 = AB[mid][AB_B_IDX]

        print(max(mx, mx2) - min(mn, mn2) + 1)


if __name__ == '__main__':
    main()

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

if N % 2 == 0:
    print(len(set(a + b for a, b in product(range(A[N // 2 - 1], A[N // 2] + 1), range(B[N // 2 - 1], B[N // 2] + 1)))))
else:
    print(B[N // 2] - A[N // 2] + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
min = [0] * (N+1)
max = [0] * (N+1)

for i in range(N):
    min[i+1], max[i+1] = map(int, input().split())
    
if N % 2 == 1:
    count = max[int((N+1)/2)] - min[int((N+1)/2)] + 1

else:
    count = 0
    data = []
    for i in range(min[int(N/2)], max[int(N/2)]+1):
        for j in range(min[int(N/2)+1], max[int(N/2)+1]+1):
            temp = (i + j)/2
            if temp not in data:
                count += 1
                data.append(temp)
                
        
print(count)

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 = r[0] - l[1] + 1
        print(nl*nr - ol*ol)




# print(intervals)

Submission status: Wrong Answer

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

if n % 2 == 1:
    print(abs(b[n//2] - a[n//2]) + 1)
else:
    tmp = [a[n // 2], a[n // 2 - 1], b[n // 2], b[n // 2 - 1]]
    tmp.sort()
    print(int(abs((tmp[0] + tmp[1]) / 2 - (tmp[2] + tmp[3]) / 2) / 0.5) + 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:
    ans = (right-left)*2-1

    c = 0
    for i in range(n):
        if num[i][0] <= left:
            c += 1
    if c >= n//2 + 1:
        ans += 1

    c = 0
    for i in range(n):
        if num[i][1] >= right:
            c += 1
    if c >= n//2 + 1:
        ans += 1
    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 + 2:
                    r = E
                    flag = 1
                    break
            if flag:
                break
        while que and not flag:
            E = heappop(que)
            end += 1
            now -= 1
            if end >= n//2+1:
                r = E
                break
        print(r-l+1)
    if n%2 == 0:
        l1,l2,r1,r2 = 0,0,0,0
        flag = 0
        for i in range(n):
            left = ab[i][0]
            now += 1
            heappush(que,ab[i][1])
            while left > que[0]:
                E = heappop(que)
                end += 1
                now -= 1
                if now + end >= n//2 and l1 == 0:
                    l1 = left
                if now + end >= n//2+1 and l2 == 0:
                    l2 = left
                if end == n//2:
                    r1 = E
                if end == n//2+1:
                    r2 = E
                    flag = 1
                    break
                if flag:
                    break
        while que and not flag:
            E = heappop(que)
            end += 1
            now -= 1
            if end == n//2:
                r1 = E
            if end == n//2+1:
                r2 = E
                break
        print((r1+r2)-(l1+l2)+1)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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


def resolve():

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

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


resolve()

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

right = 0
left = 0

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if(n%2==0 and i==n//2-1):
        ans=b-a+2
    if(n%2!=0 and i==n//2):
        ans=b-a+1
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=set([j for i in A for j in i])
    flat=sorted(list(flat))
    if len(flat)>=3:
        if flat[-2]==flat[1]:
            print(1)
        else:
            print(flat[-2]-flat[1]+1)
    else:
        print(1)
else:
    flat=set([j for i in A for j in i])
    flat=sorted(list(flat))
    if len(flat)>=3:
        if flat[-2]==flat[1]:
            print(3)
        else:
            print((flat[-2]-flat[1])*2+1) 
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

n = int(input())
li = [input().split() for _ in range(n)]
a_li = sorted([int(x[0]) for x in li])
b_li = sorted([int(x[1]) for x in li], reverse=True)
if n%2 == 0:
    hn = int(n/2)
else:
    hn = int((n+1)/2)
s = b_li[hn-1]+b_li[hn]-a_li[hn-1]-a_li[hn]+1
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
print(3)
#print(n, ab)
#90
#9900

Submission status: Wrong Answer

Solution code:
N = int(input())
L = list()
for _ in range(N):
    A, B = map(int, input().split())
    L.append((A, B))
L = sorted(L, key=lambda x: x[0])

if N%2 == 1:
    W = L[N//2]
    print(W[1] - W[0] + 1)
else:
    W = L[N//2 - 1]
    V = L[N//2]
    ans = max(W[1] - W[0] + 1, V[1] - V[0] + 1)
    print(ans + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from statistics import median

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

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

ans = int(median(B)-median(A))
if N%2==0:
    ans = ans*2
print(ans+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
B = A[:]
A.sort(key=lambda x: x[0])
B.sort(key=lambda x: x[1])

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

Submission status: Wrong Answer

Solution code:
import math

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

A.sort()
B.sort()

midA = A[(N+1)//2 - 1] if N % 2 == 1 else (A[N//2 - 1] + A[N//2])/2
midB = B[(N+1)//2 - 1] if N % 2 == 1 else (B[N//2 - 1] + B[N//2])/2

ans = 0
if isinstance(midA, float):
    if not midA.is_integer():
        midA = math.ceil(midA)
        ans += 1
if isinstance(midB, float):
    if not midB.is_integer():
        midB = math.floor(midB)
        ans += 1

if max(A) <= min(B):
    ans += min(B) - max(A) + 1
    if midA < max(A):
        ans += max(A) - midA
    if midB > min(B):
        ans += midB - min(B)
else:
    ans += max(A) - min(B) + 1
    if midA < min(B):
        ans += min(B) - midA
    if midB > max(A):
        ans += midB - max(A)


print(ans)

Submission status: Wrong Answer

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

    low.sort()
    high.sort()
    if n % 2:
        print(high[(n+1)//2-1] - low[(n+1)//2-1] + 1)
    else:
        hh = (high[(n)//2-1] + high[(n)//2]) / 2
        ll = (low[(n)//2-1] + low[(n)//2]) / 2
        print(int(hh - ll)*2 + 1)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import defaultdict

N = int(input())

AB = [tuple(map(int, input().split())) for _ in range(N)]
ALL = []
ALL_append = ALL.append
for i in range(N):
    a = AB[i][0]
    b = AB[i][1]
    ALL_append((a, i))
    ALL_append((b, i))

ALL.sort()
# print (ALL)
dic = defaultdict(int)
for i, x in enumerate(ALL):
    dic[x] = i

lst1 = [0] * (2 * N + 1)
lst2 = [0] * (2 * N + 1)

for i in range(N):
    a = AB[i][0]
    b = AB[i][1]
    lst1[dic[(a, i)]] += 1
    lst2[2 * N - dic[(b, i)]] += 1
# print (dic)
for i in range(2 * N):
    lst1[i + 1] += lst1[i]
    lst2[i + 1] += lst2[i]

# print (lst1)
# print (lst2)

if N % 2 == 1: #奇数 -->一意に決まる時
    left = bisect_left(lst1, N // 2 + 0.5)
    right = 2 * N - bisect_left(lst2, N // 2 + 0.5)
    # print (left, right)
    upper = ALL[right][0]
    lower = ALL[left][0]
    print (upper - lower + 1)
else:
    left1 = bisect_left(lst1, N // 2 - 0.5)
    left2 = bisect_left(lst1, N // 2 + 0.5) - 1
    right1 = 2 * N - bisect_left(lst2, N // 2 - 0.5)
    right2 = 2 * N - (bisect_left(lst2, N // 2 + 0.5) - 1)
    # print (left1, left2, right1, right2)
    # print (ALL[left1], ALL[left2], ALL[right1], ALL[right2])

    min_ = ALL[left1][0] + ALL[right2][0]
    max_ = ALL[left2][0] + ALL[right1][0]
    # print (min_, max_)
    print (max_ - min_ + 1)

Submission status: Wrong Answer

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

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

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

L1.sort()
L2.sort()

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
AS = []
BS = []
for i in range(N):
    A, B = [int(x) for x in input().split()]
    AS.append(A)
    BS.append(B)
AS2 = AS[:]
AS2.sort()

BS2 = BS[:]
BS2.sort()

if N % 2 == 0:
    lower = AS2[N // 2]
    upper = BS2[-N // 2]
    print((upper - lower) * 2 + 1)
else:
    lower = AS2[N // 2]
    upper = BS2[-N // 2]
    print(upper - lower + 1)

Submission status: Wrong Answer

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

N = int(input())

ab = []

for i in range(N):
  ab.append(tuple(map(int,input().split())))
  
import statistics
import math

am = statistics.median([i[0] for i in ab])
bm = statistics.median([i[1] for i in ab])

if N%2==1:
  print(bm-am+1)
else:
  print(int(bm-am+2))

Submission status: Wrong Answer

Solution code:
import math

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

list_A.sort()
list_B.sort()

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

print(_max-_min+1)

Submission status: Wrong Answer

Solution code:
#!/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)]

ab.sort(key=lambda x:x[0])
if n % 2:
    print(ab[n//2][1] - ab[n//2][0] + 1)
else:
    xa, xb = ab[n//2-1]
    ya, yb = ab[n//2]
    if ya > xb:
        print((xb - xa + 1) * (yb - ya + 1))
    else:
        ans = (xb - xa + 1) * (yb - ya + 1)
        ans -= (xb - ya + 1)
        print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ls=[list(map(int,input().split())) for i in range(N)]
ls_a=sorted([ls[i][0] for i in range(N)])
ls_b=[ls[i][1] for i in range(N)][::-1]

if N%2==1:
  print(ls_b[(N-1)//2]-ls_a[(N-1)//2]+1)
else:
  p=(ls_a[N//2-1]+ls_a[N//2])/2
  q=(ls_b[N//2-1]+ls_b[N//2])/2
  print(int((q-p)*2+1))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from bisect import bisect_left

N = int(input())
l, r = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    l[i], r[i] = map(int, input().split())
# l の小さい順にソート
l, r = zip(*sorted(zip(l, r)))
#print(l, r)

# 検証のため r を小さい順にソートしてひとつのリストとして持っておく
r_list = sorted(deepcopy(r))

if N%2 == 1:
    # N が奇数のとき
    rm_ind = bisect_left(r_list, r[N//2])
    lm, rm = l[N//2], r[N//2]
    rm = r[rm_ind]

    #print(lm, rm)
    print(max(0, rm-lm+1))
else:
    # N が偶数のとき
    lm_l = l[N//2-1]
    rm_l_ind = bisect_left(r_list, r[N//2-1])
    rm_l = r[rm_l_ind]

    lm_h = l[N//2]
    rm_h_ind = bisect_left(r_list, r[N//2])
    rm_h = r[rm_h_ind]

    lm = (lm_l + lm_h)/2
    rm = (rm_l + rm_h)/2

    # 0.5 刻みで増えることに注意
    #print(lm, rm)
    print(max(0, int((rm-lm+0.5) * 2)))

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
    a = A_sorted[n-1]
    b = B_sorted[-n]

Submission status: Wrong Answer

Solution code:
import bisect

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A, B = [], []
    for _ in range(N):
        a, b = ZZ()
        A.append(a)
        B.append(b)
    A.sort()
    B.sort()
    midA = A[N//2] if N%2 == 1 else (A[N//2-1] + A[N//2])//2
    midB = B[N//2] if N%2 == 1 else (B[N//2-1] + B[N//2] + 1)//2
    print(max(0, midB-midA+1))

    return

if __name__ == '__main__':
    main()

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())
A = []
B = []
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    ans += b - a
    A.append(a)
    B.append(b)

# AB = [[int(x) for x in input().split()] for _ in range(N)]

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

else:
    ans += 1
print(ans)

Submission status: Wrong Answer

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



if __name__ == '__main__':
    main()

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=[]
    for i in range(n):
        l.append(mdata())
    l.sort()
    if n%2!=0:
        a,b=l[n//2]
        cnt=b-a+1
        out(cnt)
    else:
        a1,b1=l[n//2-1]
        a2,b2=l[n//2]
        out(int(((b1+b2)/2-(a1+a2)/2)*2+1))


if __name__ == '__main__':
    main()

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:
    l=ll+rl
    r=rr+lr
    print(r-l+1)

Submission status: Wrong Answer

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

for a, b in AB:
    right.append(b)
    left.append(a)
right.sort(reverse=True)
left.sort()
if N%2==0:
    n = N//2-1
    print((right[n]-left[n])*2-1)
else:
    n = N//2
    print(right[n]-left[n]+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:
    A,B = ABs[N//2]
    print(B-A+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:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A, B = [], []
for i in range(N):
	a, b = rl()
	A.append(a)
	B.append(b)

A.sort()
B.sort(reverse=True)

i = (N-1)//2

print(B[i]-A[i]+1)