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

n = int(input())

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

kugiri = set(kugiri)
status_dict = {}
for key in kugiri:
    status_dict[key] = [0, 0]

for a, b in pairs:
    status_dict[a][0] += 1
    status_dict[b][1] += 1

n_kugiri = len(kugiri)
kugiri = sorted(kugiri)
nums = [0] * n_kugiri

count = 0
for i, key in enumerate(kugiri):
    na, nb = status_dict[key]
    count += na
    j = kugiri.index(key)
    nums[j] = count 

    count -= nb


#for a, b in pairs:
#    ai = kugiri.index(a)
#    bi = kugiri.index(b)
#    for j in range(ai, bi+1):
#        nums[j] += 1

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

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

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

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

                out += cur_out

print(out)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
# 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()

if N%2!=0:
    mini=m[N//2]
    maxi=M[-N//2]

    print(maxi-mini+1)
else:
    mini=m[N//2]
    maxi=M[-N//2]
    if maxi>=mini:
        print((maxi-mini)*2+1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import statistics

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

if n%2 == 0:
    leftId = statistics.median_high(left) - statistics.median_low(left)
    rightId = statistics.median_high(right) - statistics.median_low(right)
    print(int((rightId - leftId)*2 + 1))
else:
    leftId = statistics.median(left)
    rightId = statistics.median(right)
    while True:
        x = 1
    print(rightId - leftId + 1 - aaa)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [tuple(map(int, input().split())) for _ in range(N)]
if N == 2:
    ans = sorted(X, key=lambda x: x[1], reverse=True)[0][1] - sorted(X, key=lambda x: x[0])[0][0] + 1
else:
    ans = sorted(X, key=lambda x: x[1], reverse=True)[1][1] - sorted(X, key=lambda x: x[0])[1][0] + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    event = []
    for _ in range(n):
        a, b = map(int, input().split())
        event.append((0, a))
        event.append((1, b))
    event.sort()

    if n % 2 == 1:
        left = right = 0
        for q, v in event:
            if q == 0:
                left += 1
                if left == (n + 1) // 2:
                    L = v
            else:
                right += 1
                if right == (n + 1) // 2:
                    R = v
        print(R - L + 1)

    else:
        left = right = 0
        for q, v in event:
            if q == 0:
                left += 1
                if left == n // 2:
                    L = v
            else:
                right += 1
                if right == n // 2 + 1:
                    R = v
        print(R - L + 1)

resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())

left, right = [], []
for _ in range(N):
    A, B = map(int, input().split())
    left.append(A)
    right.append(B)

left = sorted(left)
right = sorted(right)

i = 0
while True:
    l = left[i]
    r = right[-1-i]
    if l>r:
        break
    i += 1
    if (i+1)==N:
        break

print(r-l+1)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

tips = []

for _ in range(n):
    a,b = MAP()
    tips.append((a,b))


minMed, mxMed = 0, 0

a =[]
b = []

for i in range(n):
    a.append(tips[i][0])
    b.append(tips[i][1])

a.sort()
b.sort()


if(n%2==0):
    minMed = (a[n // 2 - 1] + a[n // 2 ]) // 2
    mxMed = (b[n // 2 - 1] + b[n // 2 ]) // 2

    print(mxMed-minMed + 1 + mxMed-minMed)

else:
    minMed = a[(n + 1) // 2 -1]
    mxMed = b[(n + 1) // 2 - 1]
    print(mxMed-minMed + 1)

Submission status: Wrong Answer

Solution code:
import math


def median(array):
    if N % 2:
        return array[N // 2]
    else:
        return sum(array[N // 2 - 1: N // 2]) // 2


N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
x = median(A)
y = median(B)
if N % 2:
    print(y - x + 1)
else:
    print(y - x + 2)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [[int(i) for i in input().split()] for j in range(n)]

tmp = 1
tmp_b = ab[n-1][1]

for i in range(n):
    if tmp > ab[i][0]:
        ab[i][0] = tmp
    else:
        tmp = ab[i][0]
        
    if tmp_b < ab[n-i-1][1]:
        ab[n-i-1][1] = tmp_b
    else:
        tmp_b = ab[n-i-1][1]
        
if n % 2 == 1:
    print(ab[n//2][1]-ab[n//2][0]+1)
else:
    print(ab[n//2][1]+ab[n//2-1][1]-(ab[n//2][0]+ab[n//2-1][0])+1)

Submission status: Wrong Answer

Solution code:
import sys

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

n = N // 2 if N % 2 != 0 else N // 2 - 1
left = AB[n][0]

AB.sort(reverse=True)
right = AB[n][1]

print(right - left + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
numbers = []
for _ in range(N):
    a, b = map(int, input().split())
    numbers.append(b-a+1)
numbers.sort()  # 左を昇順ソート


if N % 2 == 1:
    print(numbers[N%2])
else:
    print(numbers[N%2] + numbers[N%2]-numbers[N%2-1] + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
single = []
answer_set = set()
for i in range(N):
    a, b = map(int, input().split())
    single.append(a)
    single.append(b)

single = sorted(single)
total = sum(single)
answer = 0
if N % 2 == 0:
    for i in range(2 ** (2 * N)):
        bag = []
        for j in range(2 * N):
            if ((i >> j) & 1):
                bag.append(single[j])
        if len(bag) == N:
            answer += 1
    print(int(answer / 2))
else:
    print(single[-2] - single[1] + 1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

ran = []

for a, b in ab:
    ran.append(b - a + 1)

ran.sort()

if N % 2 == 0:
    if ran[N // 2 - 1] == ran[N // 2]:
        print(2 * ran[N // 2] - 1)
    else:
        print(max(ran[N // 2 - 1], ran[N // 2]))
else:
    print(ran[N // 2])

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)
    if W[1] >= V[0]:
        print(2*ans - 1)
    else:
        print(ans + 2)

Submission status: Wrong Answer

Solution code:
n = int(input())
lister = []
for i in range(n):
    lister.append([int(i) for i in input().split()])
 
if n % 2 == 1:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(maxer- miner + 1)
else:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2 - 1][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(1 + (maxer- miner))

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = [None]*N
    B = [None]*N

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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)])
addnum = 1
if ((r0*2) % 2)>0 and ((r1*2) % 2)>0:
  mult=2
  addnum = 1
elif ((r0*2) % 2)>0:
  mult=2
  addnum = 0  
elif ((r1*2) % 2)>0:
  mult=2
  addnum = 0  
else:
  mult=1
  addnum = 1
#print(r0)
#print(r1)
mult=int((r1-r0)*mult+addnum)
print(mult)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]
ab2 = copy.deepcopy(ab)
ab = sorted(ab, key=lambda x:x[0])
ab2 = sorted(ab2, key=lambda x:x[1])
print(ab,ab2)
if n % 2 == 1:
    m = ab[n//2][0]
    M = ab2[n//2][1]
    print(M-m+1)
else:
    m = (ab[n//2][0]+ab[n//2-1][0])
    M = (ab[n//2][1]+ab[n//2-1][1])
    print(int(M-m+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()

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

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


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:
    n = len(set(A[N//2-1:]+B[:N//2+1]))
    ans = n*(n-1)//2
    print(ans)

Submission status: Wrong Answer

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


def main():

    n=int(data())
    l=[]
    l1=[]
    for i in range(n):
        l.append(mdata())
        l1.append(l[-1][1])
    l.sort(key=lambda x:x[1],reverse=True)
    l.sort(key=lambda x:x[0])
    l1.sort()
    if n%2!=0:
        a,b=l[n//2]
        b=min(b,l1[n//2])
        cnt=b-a+1
        out(cnt)
    else:
        a1,b1=l[n//2-1]
        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:
import numpy as np
from statistics import median
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
b = np.array(a)
c = list(b[:,0])
d = list(b[:,1])
x = median(c)
y = median(d)
print(int(2*(y-x)+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)]

A = [a for a,b in ab]
A.sort()
B = [b for a,b in ab]
B.sort()
if n % 2:
    print(B[n//2] - A[n//2] + 1)
else:
    xa, xb = A[n//2 - 1], B[n//2-1]
    ya, yb = A[n//2], B[n//2]
    if ya > xb:
        print((xb - xa + 1) + (yb - ya + 1))
    else:
        ans = (xb - xa + 1) + (yb - ya + 1)
        ans -= 1
        print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input(""))

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

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

    medians.append(med)

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
numbers = []
for _ in range(N):
    a, b = map(int, input().split())
    numbers.append(b-a+1)
numbers.sort()  # 左を昇順ソート

if N % 2 == 1:
    print(numbers[N%2])
else:
    print(numbers[N%2]+1)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor, gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10
    U = list()
    L = list()
    N = II()
    for i in range(N):
        a,b = LMIIS()
        U.append(b)
        L.append(a)
    U.sort()
    L.sort()
    if N % 2 == 1:
        upper = U[(1+N)//2-1]
        lower = L[(1+N)//2-1]
        print(int(upper-lower)+1)
    else:
        upper = (U[0]+U[-1])/2
        lower = (L[0] + L[-1])/2
        print(int(upper-lower)*2+1)
    
    
        




    
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [AB[i][0] for i in range(n)]
B = [AB[i][1] for i in range(n)]
# A = [(AB[i][0], i) for i in range(n)]
# B = [(AB[i][1], i) for i in range(n)]

A.sort()
B.sort()

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

print(A, B)

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

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

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:
        R=[(ll+na,rr+nb) for na,nb in AB[pos+1:]] 
        R.sort()
        M=-1
        ans=0
        for l,r in R:
            tmp=r-max(M,l)+1
            ans+=max(0,tmp)
            M=max(M,r+1)
        print(ans)
    else:
        l=ll+rl
        r=rr+lr
        print(r-l+1)

Submission status: Wrong Answer

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

if n%2==0:
  med_min=(m[n//2]+m[(n//2)-1])//2
  med_max=(M[n//2]+M[(n//2)-1])//2
else:
  med_min=m[n//2]
  med_max=M[n//2]

cnt=0
for i in range(n):
  if med_min<=m[i] and M[i]<=med_max:
    cnt+=M[i]-m[i]+1
  elif med_min<=m[i] and M[i]>med_max:
    cnt+=med_max-m[i]+1
  elif med_min>m[i] and M[i]<=med_max:
    cnt+=M[i]-med_min+1
if n%2==0:
  print(cnt)
else:
  print(cnt-1)

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
import heapq

def main():
    rng = namedtuple("rng","start end")
    n = int(input())
    starts = []
    ends = []
    middle_ind = n//2 + 1 if n%2 == 1 else n//2
    for i in range(n):
        start,end = map(int,input().split())
        heapq.heappush(starts,start)
        heapq.heappush(ends,end)

    start_counter = 0
    end_counter = 0
    over_lap = 0
    median_start = -1
    median_end = -1
    void_length = 0
    while end_counter < middle_ind:
        temp = 0
        if len(ends) <= 0 or len(starts) > 0 and starts[0] < ends[0] :
            temp = heapq.heappop(starts)
            over_lap += 1
            start_counter += 1
            if start_counter == middle_ind:
                median_start = temp
        else:
            temp = heapq.heappop(ends)
            over_lap -= 1
            end_counter += 1
        if median_start != 0 and end_counter < middle_ind and over_lap == 0:
            void_length += starts[0] - temp

        if median_start != -1 and end_counter == middle_ind:
            median_end = temp
    print(median_start,median_end,void_length)

    print(median_end - median_start - void_length+1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


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


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

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


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

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

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

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

        # print(mx, mn, mid, AB)

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

        # print(mx2, mn2, mid, AB)

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

        # print(mx, mn, mid, AB)

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

        # print(mx2, mn2, mid, AB)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
lister = []
for i in range(n):
    lister.append([int(i) for i in input().split()])
 
if n % 2 == 1:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(maxer- miner + 1)
else:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(1 + (maxer- miner)*2)

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()) 
    
Bs = sorted(B)
if N%2==1:
    maxlist = Bs[int(N-(N+1)/2):N]
    premax = min(maxlist)
    minlist = sorted(A)[:int((N+1)/2)]
    premin = max(minlist)
    print(premax-premin+1)
    
else:
    maxlist = Bs[int(N/2):N]
    premax = min(maxlist)
    minlist = sorted(A)[:int(N/2)]
    premin = max(minlist)
    num = premax-premin+1
    print(num*2-3)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())

l = []
r = []

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

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

if n%2 == 1:
    print(r[(n-1)//2]-l[(n-1)//2]+1)
else:
    l1, l2 = l[(n-2)//2], l[(n-2)//2+1]
    r1, r2 = r[(n-2)//2+1], r[(n-2)//2]
    d1, d2 = r1-l1+1, r2-l2+1
    d1, d2 = max(d1, d2), min(d1, d2)
    a1, a2 = (d1*(d1+1)//2), ((d1-d2)*(d1-d2+1)//2)
    print(a1-a2)

Submission status: Wrong Answer

Solution code:
n = int(input())
lister = []
for i in range(n):
    lister.append([int(i) for i in input().split()])
 
if n % 2 == 1:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(maxer- miner)
else:
    lister.sort(key=lambda x:x[0])
    miner = lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    print(1 + (maxer- miner)*2)

Submission status: Wrong Answer

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

A.sort()
B.sort()

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

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

    x = avr_low_B - avr_low_A + 1
    y = avr_high_B - avr_high_A + 1
    if x > y:
        x, y = y, x
    m = (y - x + 1) * x
    print(x + y - m + 1)

Submission status: Wrong Answer

Solution code:
import statistics

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

if n%2 == 0:
    leftId = statistics.median_high(left) - statistics.median_low(left)
    rightId = statistics.median_high(right) - statistics.median_low(right)
    print((rightId - leftId)*2 + 1)
else:
    leftId = statistics.median(left)
    rightId = statistics.median(right)
    while True:
        x = 1
    print(rightId - leftId + 1 - aaa)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
  a,b=map(int,input().split())
  A+=[a]
  B+=[b]
A.sort()
B.sort()
if N%2==1:
  ans=B[N//2]-A[N//2]+1
else:
  ans=(B[N//2]-A[N//2])*2+1
print(ans)

Submission status: Wrong Answer

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

n = int(input())
li = []
lin = []

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

li.sort()
lin.sort()

if n%2 == 1:
    print(lin[n//2][0]-li[n//2][0]+1)
else:
    print(lin[n//2][0]-li[(n-1)//2][0]+1)

Submission status: Wrong Answer

Solution code:
# E

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

sorted_by_A = sorted(ABs, key=lambda ab: ab[0])
sorted_by_B = sorted(ABs, key=lambda ab: ab[1])

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

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import heapq
input = lambda: sys.stdin.readline().rstrip()

INF = 10**9 + 1


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

    As = sorted(A)
    Bs = sorted(B)

    if N % 2 == 0:
        low = INF
        up = 0
        for i in range(N):
            low = min(low, A[i])
            if B[i] == Bs[0]:
                up = max(up, Bs[1])
            else:
                up = max(up, Bs[0])
        ans = up - low + 1
        ans = (ans * (ans - 1)) // 2
        print(ans)
        exit()
    else:
        i = (N - 1) // 2
        low = As[i]
        up = Bs[i]
        ans = up - low + 1
        print(ans)
        exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

if n%2==0:
    left=AB[n//2-1][0]
    right=ab[n//2][1]
    cnt=0
    cnt2=0
    
    nl=AB[0][0]
    nr=AB[0][1]
    for i in range(1,n):
        now=AB[i]
        if now[0]<=nr:
            nr=max(nr,now[1])
            #print(cnt,cnt2)
            cnt2+=cnt+min(nr,right)-max(now[0],left)
            #print(cnt,cnt2)
        else:
            #print(cnt,cnt2)
            cnt2+=cnt+min(nr,right)-max(nl,left)
            #print(cnt,cnt2)
            cnt+=max(min(nr,right)-max(nl,left)+1,0)
            #print(cnt,cnt2)
            nl=now[0]
            nr=now[1]
    #print(cnt,cnt2)
    cnt2+=cnt+min(nr,right)-max(nl,left)
    #print(cnt,cnt2)
    cnt+=max(min(nr,right)-max(nl,left)+1,0)
    #print(cnt,cnt2)
    print(cnt2)


else:
    left=AB[n//2][0]
    right=ab[n//2][1]
    cnt=0
    
    nl=AB[0][0]
    nr=AB[0][1]
    for i in range(1,n):
        now=AB[i]
        if now[0]<=nr:
            nr=max(nr,now[1])
        else:
            cnt+=max(min(nr,right)-max(nl,left)+1,0)
            nl=now[0]
            nr=now[1]
    cnt+=max(min(nr,right)-max(nl,left)+1,0)
    print(cnt)

Submission status: Wrong Answer

Solution code:
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]
    B = X[n // 2][1]
    a = X[n // 2 - 1][1] - X[n // 2 - 1][0] + 1
    b = X[n // 2][1] - X[n // 2][0] + 1
    if B <= A:
        ans += A - B + 1
        b -= ans
    
    ans = a * b - 1
else:
    ans = X[(n + 1) // 2 - 1][1] - X[(n + 1) // 2 - 1][0] + 1
    
print(ans)