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:
N = int(input())
Zahyou = set()
AB = []
for n in range(N):
    A,B = [int(hoge) for hoge in input().split()]
    AB.append((A,B))
    Zahyou.add(A)
    Zahyou.add(B+1)#Endを引いた瞬間計算からはずれる

Zahyou = sorted(Zahyou)
Zahyou.append(10**12)
Zahyoudic = dict()
for n,z in enumerate(Zahyou):
    Zahyoudic[z] = n
Start = [0] * len(Zahyou)
End = [0] * len(Zahyou)

for A,B in AB:
    Start[Zahyoudic[A]] += 1
    End[Zahyoudic[B+1]] += 1


l = 1
r = 0
curpos = 0
prepos = 0
if N%2:#奇数
    ans = 0
    Med = (N+1)//2
    for i in range(len(Zahyou)-1):
        curpos = Zahyou[i]
        areasize = Zahyou[i+1] - Zahyou[i]
        r += Start[i]
        l += End[i]
        if l<=Med<=r:
            ans += areasize
    print(ans)
else:#奇数
    ans = 0
    Med1 = N//2
    Med2 = N//2 + 1
    Med1 = 1
    Med2 = 2
    good1 = False
    good2 = False
    for i in range(len(Zahyou)-1):
        curpos = Zahyou[i]
        areasize = Zahyou[i+1] - Zahyou[i]
        r += Start[i]
        l += End[i]
        if l<=Med1<=r and not good1:
            l_1 = curpos
            good1 = True
        elif (not l<=Med1<=r) and good1:
            r_1 = curpos#半開区間
            good1 = False
        if l<=Med2<=r and not good2:
            l_2 = curpos
            good2 = True
        elif (not l<=Med2<=r) and good2:
            r_2 = curpos#半壊区間
            good2 = False      
    MinMed = (l_2 + l_1)/2
    MaxMed = (r_2 + r_1 -2)/2
    print(int((MaxMed - MinMed)//0.5 + 1))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right


def solve(n, ab_list):
    a_list = []
    b_list = []
    for a, b in ab_list:
        a_list.append(a)
        b_list.append(b)
    a_list_s = sorted(a_list)
    b_list_s = sorted(b_list)
    v_list = list(sorted(list(set(a_list_s + b_list_s))))
    m = len(v_list)

    if n % 2 == 1:
        ok_min = 10 ** 9 + 7
        ok_max = -1
        for i in range(m):
            v = v_list[i]
            lower_count = bisect_left(b_list, v)
            higher_count = n - bisect_right(a_list, v)
            if lower_count <= n // 2 and higher_count <= n // 2:
                ok_min = min(ok_min, v)
                ok_max = max(ok_max, v)
        return ok_max - ok_min + 1
    else:
        ok_min_left = 10 ** 9 + 7
        ok_max_left = -1
        ok_min_right = 10 ** 9 + 7
        ok_max_right = -1
        for i in range(m):
            v = v_list[i]
            lower_count = bisect_left(b_list, v)
            higher_count = n - bisect_right(a_list, v)
            if lower_count <= n // 2 - 1 and higher_count <= n // 2:
                ok_min_left = min(ok_min_left, v)
                ok_max_left = max(ok_max_left, v)
            if lower_count <= n // 2 and higher_count <= n // 2 - 1:
                ok_min_right = min(ok_min_right, v)
                ok_max_right = max(ok_max_right, v)
        return (ok_max_right - ok_min_right + ok_max_left - ok_min_left) + 1


def main():
    n = int(input())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, ab_list)
    print(res)


def test():
    assert solve(2, [[1, 2], [2, 3]]) == 3
    assert solve(3, [[100, 100], [10, 10000], [1, 1000000000]]) == 9991


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    t = [[int(t)for t in input().split()]for _ in [0]*n]

    t_1 = sorted(t,key=lambda a: a[0])
    t_2 = sorted(t,key=lambda b:b[1],reverse=True)

    if n%2==1:
        ans = t_2[n//2][1]-t_1[n//2][0]+1
        print(ans)
    else:
        b1 = t_2[n//2][1]
        a0 = t_1[n//2][0]

        b0 = min([a_i for a_i,b_i in t if b_i==b1])
        a1 = max([b_i for a_i,b_i in t if a_i==a0])
        ans = a1-a0+b1-b0 + 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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()
if n&1:
    print(b[n//2]-a[n//2]+1)
else:
    print(1+(b[n//2]+a[n//2])-(b[(n-1)//2]+a[(n-1)//2]))

Submission status: Wrong Answer

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

for _ in range(N):
    A,B = list(map(int,input().split()))
    conditions.append([A,B])
    
if N % 2 == 1:
    S,M = conditions[int((N + 1) / 2) - 1]
    print(M - S + 1)
    
if N % 2 == 0:
    S1,M1 = conditions[int(N / 2) - 1]
    S2,M2 = conditions[int(N / 2)]
    
    small = S1 + S2
    big = M1 + M2
    
    print(big - small + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
AA = [0]*N
BB = [0]*N
for i in range(N):
  AA[i], BB[i] = map(int,input().split())
AA_sorted = sorted(AA)
BB_sorted = sorted(BB,reverse=True)
print(AA_sorted)
print(BB_sorted)
if N%2 == 1:
  idx = int(N/2)
  N_Max = BB_sorted[idx]
  N_Min = AA_sorted[idx]
  print(N_Max-N_Min+1)
else:
  idx = int(N/2)
  N_Max = BB_sorted[idx-1]
  N_Min = AA_sorted[idx-1]
  N_Max2 = BB_sorted[idx]
  N_Min2 = AA_sorted[idx]
  Nmax = N_Max + N_Max2
  Nmin = N_Min + N_Min2
  print(Nmax-Nmin+1)

Submission status: Wrong Answer

Solution code:
import sys

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 = []
for a, b in AB:
    LINE.append((a, 0))
    LINE.append((b + 1, 1))

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:
        if p == 0:
            small_able += 1
        elif p == 1:
            small += 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:
        if p == 0:
            small_able += 1
        elif p == 1:
            small += 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(mn, mx)


print(mx - mn + 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
N = int(input())
l = -1
r = 10**10
als = [0]*N
bls = [0]*N
for i in range(N):
  a,b = map(int, input().split())
  als[i] = a
  bls[i] = b
if N%2==0:
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_right(als,s)
    if i>=N//2:
      r = s
    else:
      l = s
  A1 = r
  B1 = r+1
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_right(bls,s)
    j = N-i
    if j>N//2:
      l = s
    else:
      r = s
  A2 = r
  B2 = r+1
  ans = B2+A2-A1-B1+1
  print(ans)
else:
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_left(als,s)
    if i>N//2:
      r = s
    else:
      l = s
  A = l
  l = -1
  r = 10**10
  while l+1<r:
    s = (l+r)//2
    i = bisect_left(bls,s)
    j = N-i
    if j>N//2:
      l = s
    else:
      r = s
  B = l
  print(B-A+1)

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())
import statistics
X = statistics.median(a)
Y = statistics.median(b)
print(Y-X+1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math
import random
from decimal import Decimal
import itertools
import re
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(2147483647)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def main():
	n = I()
	A = np.zeros(n)
	B = np.zeros(n)
	for i in range(n):
			A[i], B[i] = LI()
	if n % 2 == 0:
		print(int((np.median(B)-np.median(A))*n+1))
	else:
		print(int(np.median(B)-np.median(A)+1))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import statistics
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
check = [0]*N
for i in range(N):
    check[i] = arr[i][1]-arr[i][0]+1
tmp = statistics.median(check)
print(tmp)

Submission status: Wrong Answer

Solution code:
import math
import statistics
N = int(input())
# a_min = 10**10
# a_max = -1
# b_min = 10**10
# b_max = -1
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    # a_min = min(a, a_min)
    # a_max = max(a, a_max)
    # b_min = min(b, b_min)
    # b_max = max(b, b_max)

# print([a_min, a_max], [b_min, b_max])
a_median = statistics.median(A)
b_median = statistics.median(B)
print(math.ceil(b_median) - int(a_median)+1)

Submission status: Wrong Answer

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

if n%2 == 0:
    nec = n//2
else:
    nec = n//2+1

lbuf = buf.copy()
rbuf = buf.copy()

lbuf.sort(key=lambda x:x[0])
rbuf.sort(key=lambda x:x[1])

rind = 0
lbods = []

pos = 0
fix = 0
for i in range(n):
    temp = lbuf[i][0]
    pos += 1
    if rind < n:
        while rbuf[rind][1] <= temp:
            fix += 1
            rind += 1
            if rind == n:
                break

    lbods.append([temp,pos,fix])



lbuf.sort(key=lambda x: -x[0])
rbuf.sort(key=lambda x: -x[1])

lind = 0
rbods = []

pos = 0
fix = 0
for i in range(n):
    temp = rbuf[i][1]
    pos += 1
    if lind < n:
        while lbuf[lind][0] >= temp:
            fix += 1
            lind += 1
            if lind == n:
                break

    rbods.append([temp, pos , fix])

# print(lbods)
# print(rbods)

lb = 0
rb = 0
for i in range(n):
    if lbods[i][1] == nec:
        lb = lbods[i][0]
        break

for i in range(n):
    if rbods[i][1] == nec:
        rb = rbods[i][0]
        break

print(rb-lb+1)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())

def read_int_n():
    return list(map(int, input().split()))

def read_float():
    return float(input())

def read_float_n():
    return list(map(float, input().split()))

def read_str():
    return input().strip()

def read_str_n():
    return list(map(str, input().split()))

def error_print(*args):
    print(*args, file=sys.stderr)


def main():
    n = read_int()
    al = []
    bl = []
    for i in range(n):
        a, b = read_int_n()
        al.append(a)
        bl.append(b)
    al.sort()
    al.reverse()
    bl.sort()
    out = (math.ceil(n/2) - 1)
    
    cl = al[n - 1 - out]
    ch = bl[n - 1 - out]

    if n % 2 == 1:
        print(ch - cl + 1)
    else:
        c = ch - cl + 1
        print(math.floor(c * (c-1) / 2))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
start = list()
end = list()

for i in range(N):
  A, B = map(int, input().split())
  start.append(A)
  end.append(B)
start.sort()
end.sort()
if N % 2 == 1:
  print(end[int(N/2)] - start[int(N/2)] + 1)
else:
  print((end[int(N/2)] - start[int(N/2)-1])*2 - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
X = sorted(AB, key=lambda x: x[0])
Y = sorted(AB, key=lambda x: x[1])
if n % 2 == 0:
    print((Y[n // 2][1] - X[n // 2 - 1][0] - 1) * 2 + 1)
else:
    print(Y[n // 2][1] - X[n // 2][0] + 1)

Submission status: Wrong Answer

Solution code:
#!python3

import bisect

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A, B = [None] * N, [None] * N
for i in range(N):
    A[i], B[i] = LI()


# def upper_limit():
#     l, r = 0, 10 ** 9 + 1
#     while r - l > 1:
#         x = (l + r) // 2
#         i = bisect.bisect_left(B, x)
#         if N % 2 == 1:
#             if i <= N // 2:
#                 l = x
#             else:
#                 r = x
#         else:
#             if i < N // 2:
#                 l = x
#             elif i == N // 2:


def limit(l):
    i = N // 2
    if N % 2 == 0:
        return (l[i - 1] + l[i] + 1) // 2
    else:
        return l[i]


def main():
    A.sort()
    B.sort()
    ans = limit(B) - limit(A) + 1
    if N % 2 == 0:
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

A.sort()
B.sort()

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

if n % 2 != 0:
    left = la[n//2]
    right = lb[n//2]
    print(right-left+1)
else:
    left = (la[n//2]+la[n//2-1])/2
    right = (lb[n//2]+lb[n//2-1])/2
    print(int(right-left)*2+1)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

list = []

for i in range(N):
    list.append(A[i][0])
    list.append(A[i][1])

list.sort()


if(N%2 == 1):
    ans = list[N+1] - list[N-2] + 1

else:
    temp = list[N+1] - list[N-2] + 1
    ans = temp*(temp - 1)//2

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())

a = []
for i in range(N):
    ab = list(map(int,(input().split())))
    a.append(ab)

if N%2 == 1:
    a.sort()
    l = a[(N-1)//2][0]
    #print(a)
    a.sort(key=lambda x:x[1])
    r = a[(N-1)//2][1]
    print(r-l+1)
else:
    a.sort()
    l1 = a[N//2-1][0]
    l2 = a[N//2][0]
    #print(a)
    a.sort(key=lambda x:x[1])
    r1 = a[N//2][1]
    r2 = a[N//2-1][1]
    c = l1 + r2
    d = l2 + r1
    print(d-c+1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = set()
    B = set()

    for _ in range(N):
        a, b = il()
        A.add(a)
        B.add(b)

    ret = set()
    for a in A:
        for b in B:
            ret.add(Decimal((a + b) / 2))
    print(len(ret))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

else:
    info = sorted(info)
    l, lmax = info[n // 2 - 1]
    info = sorted(info)[::-1]
    rmin, r = info[n // 2 - 1]
    print((lmax - l + 1) + (r - rmin + 1) - 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 = Decimal(sum(B))/Decimal(2) - Decimal(sum(A))/Decimal(2)
    ans /= Decimal(0.5)
    print(int(ans))
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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 = []
for a, b in AB:
    LINE.append((a, 0))
    LINE.append((b + 1, 1))

LINE.sort()

ans = 0

small = 0
small_able = 0
prevx = -1


if N % 2 == 1:

    mn = 10 ** 10
    mx = 0

    flg = True

    for x, p in LINE:
        if p == 0:
            small_able += 1
        elif p == 1:
            small += 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 = True
    flg_1 = True

    for x, p in LINE:
        if p == 0:
            small_able += 1
        elif p == 1:
            small += 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())
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 == 1:
  ans = B[(n - 1) // 2] - A[(n - 1) // 2] + 1

else:
  ans = B[n // 2] - A[n // 2] + 1
  ans *= 2 
  ans -= 1

  if A[n // 2] != A[n // 2 - 1]:
    ans += 1

  if B[n // 2] != B[n // 2 - 1]:
    ans -= 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)
    lin.append(b)

li.sort()
lin.sort()

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

# 取りうる最小の中央値と最大の中央値を計算
# 偶数のときは0.5, 奇数のときは1
m = np.median(AB[:, 0])
M = np.median(AB[:, 1])

if N % 2 == 0:
    print(int(M - m) * 2 + 1)
else:
    print(int(M - m) + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


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:
    min_x = (A[N//2] + A[(N//2)-1]) / 2
    max_x = (B[N//2] + B[(N//2)-1]) / 2
    # print(min_x, max_x)
    print((max_x - min_x)/0.5 + 1)
else:
    min_x = A[N//2]
    max_x = B[N//2]
    # print(min_x, max_x)
    print(max_x - min_x + 1)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline
 
N=int(readline())
A = [None] * N
B = [None] * N
for i in range(N):
  a,b = map(int,readline().split())
  A[i] = [a,b]
  B[i] = [b,a]

A = sorted(A,key = lambda x:x[0])
B = sorted(B,key = lambda x:x[0])

if N % 2 == 1:
  minval = A[N // 2][0]
  maxval = B[N // 2][0]
  print(max(maxval - minval + 1,0))
else:
  minval = A[(N - 1) // 2][0]
  minvalend = A[(N - 1) // 2][1]
  
  maxval = B[(N) // 2][0]
  maxvalstart = B[(N) // 2][1]

  print((minvalend - minval + 1) * (maxval - maxvalstart + 1))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
A = []
B = []
for i in range(n):
    a,b = map(int,readline().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
#奇数であると前提してまずは実装しきっちゃう
if not even(n):
    lower = A[n//2]
    upper = B[n//2]
    print(upper-lower+1)
else:
    l1 = A[n//2-1]
    l2 = A[n//2]
    u1 = B[n//2]
    u2 = B[n//2-1]

    a = u1-l1+1
    b = abs(l2-u2)+1
    print(a+b-1)

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    ab = [MII() for _ in range(n)]
    ab.sort(key=lambda x: (x[0], x[1]))
    if n%2==1:
        l1, r1 = ab[n//2][0], ab[n//2][-1]
        print(r1-l1+1)
    else:
        l1, r1 = ab[(n//2)-1][0], ab[(n//2)-1][-1]
        l2, r2 = ab[(n//2)][0], ab[(n//2)][-1]
        print((r1+r2)-(l1+l2)+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if N % 2 == 0:
  k1 = int(N/2-1)
  k2 = int(N/2)
  pattern = set()
  for i in range(AB[k1][0], AB[k1][1]+1):
    for j in range(AB[k2][0], AB[k2][1]+1):
      pattern.add(i+j)
  
  print(len(pattern))
else:
  k = int((N+1)/2)-1
  A = AB[k][0]
  B = AB[k][1]
  print(B-A+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a_arr=[]
b_arr=[]

for i in range(n):
    a,b=map(int,input().split())
    a_arr.append(a)
    b_arr.append(b)
if n%2 !=0:
    ans=b_arr[int((n+1)/2)-1] - a_arr[int((n+1)/2)-1] +1
else:
    ans=b_arr[int(n/2)]-a_arr[int(n/2)-1] +1
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
ABs_desc = deepcopy(ABs)
ABs.sort() #Aでソート
ABs_desc.sort(key=lambda x: x[1],reverse=True)
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())
la, lb = [], []
for _ in range(n):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)

la.sort()
lb.sort(reverse=True)

if n % 2 == 1:
    i = n // 2 + 1
    md = la[i - 1]
    mu = lb[i - 1]
    answer = mu - md + 1
else:
    i = n // 2
    md = la[i - 1]
    mu = lb[i - 1]
    answer = 2 * (mu - md) - 1

print(answer)

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() #Aでソート
ABs_desc.sort(key=lambda x: x[1])
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:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    ab = [MII() for _ in range(n)]
    ab.sort(key=lambda x: (x[0], x[1]))
    if n%2==1:
        print(ab[n//2][1]-ab[n//2][0]+1)
    else:
        l1, r1 = ab[(n//2)-1][0], ab[(n//2)-1][-1]
        l2, r2 = ab[(n//2)][0], ab[(n//2)][-1]
        print((r1+r2)-(l1+l2)+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
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 = (sum(A)/2 - sum(B)/2)
    ans /= 0.5
    print(int(ans))
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)

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)
a.sort()
b.sort()
n = len(a)
if n%2!=0:
    x = n//2
    print(b[x]-a[x]+1)
else:
    x = n//2
    y = x-1
    a1 = (a[y]+a[y])/2
    b1 = (b[x]+b[y])/2
    ans = (b1-a1)/0.5
    print(int(ans))

Submission status: Wrong Answer

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

A.sort()
B.sort()

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

Submission status: Wrong Answer

Solution code:
import statistics
N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
left = sum(A)
right = sum(B)
if N%2 == 0:
  print(right-left+1)
else: 
  print(statistics.median(B)-statistics.median(A)+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
A = [AB[i][0] for i in range(n)]
B = [AB[i][1] for i in range(n)]
# A = [(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)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
if n%2==0:
  l=0
  r=10**9+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2 or cnt2>n//2-1:
      r=mid
    else:
      l=mid
  r1=l
  l=0
  r=r1+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2 or cnt2>n//2-1:
      l=mid
    else:
      r=mid
  l1=r
  l=0
  r=10**9+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2-1 or cnt2>n//2:
      r=mid
    else:
      l=mid
  r2=l
  l=0
  r=r2+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2-1 or cnt2>n//2:
      l=mid
    else:
      r=mid
  l2=r
  print((r1+r2)-(l1+l2)+1)  
elif n%2==1:
  l=0
  r=10**9+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2 or cnt2>n//2:
      r=mid
    else:
      l=mid
  l1=l
  r1=r
  l=0
  r=l1+1
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    cnt2=0
    cnt3=0
    for a,b in arr:
      if mid<a:
        cnt1+=1
      elif mid>b:
        cnt2+=1
      else:
        cnt3+=1
    if cnt1>n//2 or cnt2>n//2:
      l=mid
    else:
      r=mid
  l2=l
  r2=r
  print(l1-r2+1)

Submission status: Wrong Answer

Solution code:
def e_count_median():
    N = int(input())
    # Intervals = [[int(i) for i in input().split()] for j in range(N)]
    Min, Max = [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        Min.append(a)
        Max.append(b)

    if N % 2 == 0:
        return sum(Max) - sum(Min) + 1

    Min.sort()
    Max.sort()
    median_min, median_max = Min[N // 2], Max[N // 2]
    return median_max - median_min + 1

print(e_count_median())

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    AB = [list(map(int, input().split())) for _ in range(n)]
    if n % 2 == 1:
        m = (n + 1) // 2
        a, b = AB[m-1]
        print(b - a + 1)
    else:
        a, b = AB[n//2-1]
        c, d = AB[n//2 ]
        print(b-a+d-c+1)
main()