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: Accepted

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

#print(ma,mi,d)

Submission status: Accepted

Solution code:
import sys
input = lambda:sys.stdin.readline().strip()
n = int(input())
a = [0]
b = [0]
for i in range(n):
    ai,bi = map(int,input().split())
    a.append(ai)
    b.append(bi)
a.sort()
b.sort()
if n&1:
    print(b[(n+1)//2]-a[(n+1)//2]+1)
else:
    print((b[n//2]+b[(n//2)+1])-(a[n//2]+a[(n//2)+1])+1)

Submission status: Accepted

Solution code:
n = int(input())

a = []
b = []

for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

a.sort()
b.sort()

x, y = 0, 0

if n % 2 == 1:
    x = b[n//2]
    y = a[n//2]
else:
    x = b[n//2] + b[n//2-1]
    y = a[n//2] + a[n//2-1]

print(x-y+1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n = ni()
    bo = []
    up = []
    for _ in range(n):
        a,b = na()
        bo += [a]
        up += [b]
    bo.sort()
    up.sort()
    
    if n%2 == 1:
        print(up[n//2] - bo[n//2] + 1)
    else:
        pre_b, pre_u = bo[n//2 - 1], up[n//2 - 1]
        nex_b, nex_u = bo[n//2], up[n//2]
        print((pre_u+nex_u) - (pre_b+nex_b) + 1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
for x in range(n):
    tmp = list(map(int, input().split()))
    a[x] = tmp[0]
    b[x] = tmp[1]

a.sort()
b.sort()
if n % 2 == 1:
    l = a[n // 2]
    r = b[n // 2]
    print(r - l + 1)
else:
    l1, l2 = a[n // 2 - 1], a[n // 2]
    r1, r2 = b[n // 2 - 1], b[n // 2]
    print((r1 + r2) - (l1 + l2) + 1)

Submission status: Accepted

Solution code:
import statistics

N = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
AB = [list(map(int, input().split())) for i in range(N)]
AB = list(zip(*AB))

low = statistics.median(AB[0])
high = statistics.median(AB[1])

if len(AB[0])%2 ==0:
    print(int(2*(high-low)+1))
else:
    print(high-low+1)

Submission status: Accepted

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

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

A = []
B = []
for a, b in ab:
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if N % 2 == 0:
    a1 = A[N // 2 - 1]
    b1 = B[N // 2 - 1]
    a2 = A[N // 2]
    b2 = B[N // 2]
    xa = (a2 + a1) / 2
    xb = (b2 + b1) / 2
    print(int((xb - xa) * 2 + 1))
else:
    xa = A[N // 2]
    xb = B[N // 2]
    print(xb - xa + 1)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
a = [info[i][0] for i in range(n)]
b = [info[i][1] for i in range(n)]

a = sorted(a)
b = sorted(b)
if n % 2 == 1:
    l = a[n // 2]
    r = b[n // 2]
    print(r - l + 1)
else:
    l1, l2 = a[n // 2 - 1], a[n // 2]
    r1, r2 = b[n // 2 - 1], b[n // 2]
    print((r1 + r2) - (l1 + l2) + 1)

Submission status: Accepted

Solution code:
n = int(input())
lower, upper = [], []
for _ in range(n):
    a, b = map(int, input().split())
    lower.append(a)
    upper.append(b)
lower.sort()
upper.sort()
if n % 2 == 1:
    mid = n // 2
    median_min = lower[mid]
    median_max = upper[mid]
else:
    mid = n // 2 - 1
    median_min = lower[mid] + lower[mid + 1]
    median_max = upper[mid] + upper[mid + 1]
print(median_max - median_min + 1)

Submission status: Accepted

Solution code:
lower, upper = [], []
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    lower.append(a)
    upper.append(b)
lower.sort()
upper.sort(reverse=True)
if n % 2 == 1:
    mid = n // 2
    median_min = lower[mid]
    median_max = upper[mid]
else:
    mid = n // 2 - 1
    median_min = lower[mid] + lower[mid + 1]
    median_max = upper[mid] + upper[mid + 1]
print(median_max - median_min + 1)

Submission status: Accepted

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 = sorted( A )
B = sorted( B )

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

Submission status: Accepted

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

if N%2 == 1:
    ans = B[N//2] - A[N//2] + 1
else:
    a = A[N//2-1] + A[N//2]
    b = B[N//2-1] + B[N//2]
    ans = b - a + 1

print(ans)

Submission status: Accepted

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

def solve():
    N = int(input())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    def isOK_LE(X, thre):
        num = 0
        for A, B in ABs:
            if A <= X:
                num += 1
        return num >= thre

    def isOK_GE(X, thre):
        num = 0
        for A, B in ABs:
            if X <= B:
                num += 1
        return num >= thre

    def binS_LE(isOK, thre):
        ng, ok = 0, 10**9+1
        while abs(ok-ng) > 1:
            mid = (ng+ok) // 2
            if isOK(mid, thre):
                ok = mid
            else:
                ng = mid
        return ok

    def binS_GE(isOK, thre):
        ng, ok = 10**9+1, 0
        while abs(ok-ng) > 1:
            mid = (ng+ok) // 2
            if isOK(mid, thre):
                ok = mid
            else:
                ng = mid
        return ok

    if N % 2:
        num = (N+1)//2
        mn = binS_LE(isOK_LE, num)
        mx = binS_GE(isOK_GE, num)
#        print('mn:', mn, '/ mx:', mx)
#        print(mx-mn)
        return mx-mn+1
    else:
        num = N//2
        mn1 = binS_LE(isOK_LE, num)
        mx1 = binS_GE(isOK_GE, num+1)
        mn2 = binS_LE(isOK_LE, num+1)
        mx2 = binS_GE(isOK_GE, num)
#        print('mn1:', mn1, '/ mx1:', mx1)
#        print('mn2:', mn2, '/ mx2:', mx2)
        mn = mn1+mn2
        mx = mx1+mx2
#        print('mn:', mn, '/ mx:', mx)
#        print(mx-mn)
        return mx-mn+1


ans = solve()
print(ans)

Submission status: Accepted

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[x]+a[y])/2
    b1 = (b[x]+b[y])/2
    ans = (b1-a1)/0.5
    print(int(ans)+1)

Submission status: Accepted

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

if n % 2 == 1:
    ab.sort(reverse=True,key=lambda x: x[1])
    max_ab = ab[n//2][1]
    ab.sort(reverse=True,key=lambda x: x[0])
    print(max_ab-ab[n//2][0]+1)
else:
    ab.sort(reverse=True,key=lambda x: x[1])
    ab1 = ab[n//2][1]
    ab2 = ab[n//2-1][1]
    ab.sort(key=lambda x: x[0])
    ab3 = ab[n//2][0]
    ab4 = ab[n//2-1][0]
    
    print(ab1+ab2-(ab3+ab4)+1)

Submission status: Accepted

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

def median(li):
    if n%2==1:
        return li[n//2]
    else:
        return sum(li[n//2-1:n//2+1])
print(median(B)-median(A)+1)

Submission status: Accepted

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

Submission status: Accepted

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


A.sort()
B.sort()
if N % 2 == 1:
    print(B[(N+1)//2 - 1] - A[(N+1)//2 - 1] + 1)
else:
    d_B_med = (B[N//2 - 1] + B[N//2])
    d_A_med = (A[N//2 - 1] + A[N//2])
    print(d_B_med - d_A_med + 1)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
N = int(input())
A = [0]*N
B = [0]*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:
    temp = N//2
    m = (A[temp]+A[temp-1])/2
    M = (B[temp]+B[temp-1])/2
    print(int((M-m+1/2)//(1/2)))
else:
    temp = N//2
    print(B[temp]-A[temp]+1)

Submission status: Accepted

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

def mid(AB, idx):
    if N % 2 == 0:
        return (AB[N//2-1][idx] + AB[N//2][idx]) / 2
    else:
        return AB[(N+1)//2-1][idx]

AB.sort()
amid = mid(AB, 0)
AB.sort(key=lambda x: x[1])
bmid = mid(AB, 1)
tmp = 1 if N % 2 == 1 else 2
print(int(tmp * (bmid - amid) + 1))

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
mins, maxs = [], []
for i in range(N):
    a, b = map(int, input().split())
    mins.append(a)
    maxs.append(b)
mins.sort()
maxs.sort()
if N % 2 == 0:
    mincn = (mins[N//2-1] + mins[N//2])
    maxcn = (maxs[N//2-1] + maxs[N//2])
else:
    mincn = mins[N//2]
    maxcn = maxs[N//2]
print(maxcn - mincn + 1)

Submission status: Accepted

Solution code:
from math import *
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)
A.sort();B.sort()
if N%2:
    ans=median(B)-median(A)+1
else:
    ans=(median(B)-median(A))*2+1
print(int(ans))

Submission status: Accepted

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

a_list.sort()
b_list.sort()

a_m = a_list[N // 2 - 1] + a_list[N // 2] if N % 2 == 0 else a_list[(N + 1) // 2 - 1]
b_m = b_list[N // 2 - 1] + b_list[N // 2] if N % 2 == 0 else b_list[(N + 1) // 2 - 1]
a_m /= 2
b_m /= 2

print(int((b_m - a_m) / 0.5) + 1)

Submission status: Accepted

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]
    miner += lister[n//2][0]
    lister.sort(key=lambda x:x[1])
    maxer = lister[n//2][1]
    maxer += lister[n//2 - 1][1]
    print(1 + (maxer- miner))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = []
b_list = []
for i in range(0, n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 0:
    x1 = n // 2 - 1
    x2 = n // 2
    print(b_list[x2] - a_list[x2] + b_list[x1] - a_list[x1] + 1)
else:
    x = n // 2
    print(b_list[x] - a_list[x] + 1)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.zeros(N)
B = np.zeros(N)
for i in range(N):
    A[i], B[i] = map(int, input().split())

am = np.median(A)
bm = np.median(B)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import *
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)
A.sort();B.sort()
if N%2:
    ans=B[(N+1)//2-1]-A[(N+1)//2-1]+1
else:
    ans=1+((B[N//2-1]+B[N//2]))-((A[N//2-1]+A[N//2]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A,B = LIR(N,2)
A.sort()
B.sort()

if N%2 == 1:
    min_ = A[(N-1)//2]
    max_ = B[(N-1)//2]
    print(max_-min_+1)
else:
    smin_ = A[N//2-1]+A[N//2]
    smax_ = B[N//2-1]+B[N//2]
    print(smax_-smin_+1)

Submission status: Accepted

Solution code:
n = int(input())

A,B = [],[]

for _ in range(n):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()

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

Submission status: Accepted

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

if n % 2 ==0:
    s = a[n//2 -1][0]
    e = b[n//2 -1][0]
    s2 = a[n//2][0]
    e2 = b[n//2][0]
    ans = e+ e2 -s-s2+1   
else:
    s = a[(n+1)//2 -1][0]
    e = b[(n+1)//2 -1][0]
    ans = e-s+1
print(ans)

Submission status: Accepted

Solution code:
import heapq as hp
n = int(input())
if n%2 ==0:
    m = n//2 + 1
else:
    m = (n+1) //2
a,b = [],[]
for i in range(0,n):
    c = list(map(int, input().split()))
    a.append(c[0])
    b.append(c[1])
la = hp.nlargest(m,a)
lb = hp.nlargest(m,b)
if n%2 == 0:
    c = la[-1] + la[-2] 
    d = lb[-1] + lb[-2] 
    print(d-c+1)
else:
    print(lb[-1]-la[-1]+1)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N=II()
AS=[]
BS=[]
for i in range(N):
    A,B=LI()
    AS.append(A)
    BS.append(B)
AS.sort()
BS.sort()
if N % 2:
    print(BS[N//2]-AS[N//2]+1)
else:
    print((BS[N//2]+BS[N//2-1]-(AS[N//2]+AS[N//2-1]))+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    import sys
    n = int(input())
    A,B = [],[]
    for i in range(n):
        a,b= map(int, input().split())
        A.append(a)
        B.append(b)
    A = sorted(A)
    B = sorted(B)
    if n%2 == 0:
        ma = (A[n//2]+A[n//2-1])/2
        mb = (B[n//2]+B[n//2-1])/2
        ans = int(2*(mb-ma) + 1)
        print(ans)
    else:
        ma = A[n//2]
        mb = B[n//2]
        ans = (mb-ma) + 1
        print(ans)
        
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


n = readint()
a = []
b = []
for i in range(n):
    x,y = readints()
    a.append(x)
    b.append(y)
a.sort()
b.sort()

if n%2==1:
    l = a[n//2]
    r = b[n//2]
    print(r-l+1)
else:
    l = a[n//2] + a[n//2-1]
    r = b[n//2] + b[n//2-1]
    print(r-l+1)

Submission status: Accepted

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


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()
x = median(A)
y = median(B)
print(y - x + 1)

Submission status: Accepted

Solution code:
import math


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


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()
x = median(A)
y = median(B)
print(y - x + 1)

Submission status: Accepted

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==0:
    sca=scb=N//2-1
    lca=lcb=N//2
    x=A[lca]+A[sca]
    y=B[lcb]+B[scb]
    print(y-x+1)
    
    
else:
    ca=cb=N//2
    ans=B[cb]-A[ca]+1
    print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

    if N % 2 == 0:
        A = [a * 2 for a in A]
        B = [b * 2 for b in B]

    A.sort()
    B.sort()

    medA = (A[(N - 1) // 2] + A[N // 2]) // 2
    medB = (B[(N - 1) // 2] + B[N // 2]) // 2

    ans = medB - medA + 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, *AB = map(int, open(0).read().split())
A, B = map(sorted, [AB[::2], AB[1::2]])
mid = n//2
a = A[mid]
b = B[mid]
if n % 2 == 0:
    a += A[mid-1]
    b += B[mid-1]
print(b-a+1)

Submission status: Accepted

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
 
def do():
    n=INT()
    A=[]
    B=[]
    for i in range(n):
        a,b=INTM()
        A.append(a)
        B.append(b)
        #print(A,B)
    A=sorted(A)
    B=sorted(B,reverse=True)
    if n%2==1:
        ta=A[n//2]
        tb=B[n//2]
        print(tb-ta+1)
    else:
        ta1=A[n//2-1]
        ta2=A[n//2]
        tb1=B[n//2-1]
        tb2=B[n//2]
        avea=(ta1+ta2)/2
        aveb=(tb1+tb2)/2
        print(int((aveb-avea)*2)+1)
        
        
    
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
X = []
As = []
Bs = []
for i in range(n):
    A, B = list(map(int, input().split()))
    As.append(A)
    Bs.append(B)
As.sort()
Bs.sort()

if n % 2 == 1:
    m = (n-1) // 2
    print(Bs[m] - As[m] + 1)
else:
    b_m = n // 2 - 1
    a_m = b_m + 1
    min_mid =  (As[b_m] + As[a_m])
    max_mid =  Bs[b_m] + Bs[a_m]
    print(max_mid - min_mid + 1)

Submission status: Accepted

Solution code:
N = int(input())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB += [(A, B)]
sortA = sorted(AB, key=lambda x: x[0])
sortB = sorted(AB, key=lambda x: x[1])
if N % 2 == 0:
    mid = N//2-1
    A11,B11 = sortA[mid]
    A12,B12 = sortA[mid+1]
    # print(A11, B11)
    # print(A12, B12)
    A1 = (A11+A12) / 2
    B1 = (B11+B12) / 2
    A21,B21 = sortB[mid]
    A22,B22 = sortB[mid+1]
    A2 = (A21+A22) / 2
    B2 = (B21+B22) / 2
    # ans = (min(B1, B2) - max(A1, A2))*2 + 1
    ans = (B2 - A1)*2 + 1
    # print(B1, B2, A1, A2, ans)
    # if ans % 1 != 0:
    #     ans += 1
else:
    mid = (N+1)//2-1
    A1,B1 = sortA[mid]
    A2,B2 = sortB[mid]
    # print(A1, A1, B1, B2)
    ans = (B2 - A1) + 1

print(int(ans))

Submission status: Accepted

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

A.sort()
B.sort()
if N%2 == 1:
    m_min = A[N//2]
    m_max = B[N//2]
    diff = m_max - m_min
    print(diff +1)
else:
    m_min = (A[N//2-1] +A[N//2])/2
    m_max = (B[N//2-1] +B[N//2])/2
    diff = m_max - m_min
    print(int(diff//0.5)+1)

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
m,M=sorted(l[::2]),sorted(l[1::2])
d=n//2
print(M[d]-m[d]+1+(M[d-1]+-m[d-1])*(n%2^1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

amax=0
bmin=10**100
arra=[]
arrb=[]
for i in range(n):
    a,b=mii()
    arra.append(a)
    arrb.append(b)

arra.sort()
arrb.sort()

if n%2==1:
    p=arra[n//2 ]
    q=arrb[n//2 ]

    print(q-p+1)
else:
    p=(arra[n//2 -1]+arra[n//2])
    q=(arrb[n//2 -1]+arrb[n//2])
    #print(p,q,arra[n//2-1])
    print(q-p+1)

Submission status: Accepted

Solution code:
n, *AB = map(int, open(0).read().split())
A, B = map(sorted, [AB[::2], AB[1::2]])
mid = n//2
if n % 2 == 0:
    a0, a1 = A[mid-1], A[mid]
    b0, b1 = B[mid-1], B[mid]
    print(b0+b1 - (a0+a1) + 1)
else:
    print(B[mid] - A[mid] + 1)

Submission status: Accepted

Solution code:
import statistics
import math
from decimal import *
N = int(input())

n =[]
m =[]

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

nmean = Decimal(statistics.median(n))
mmean =Decimal(statistics.median(m))

if N%2 == 1:
    print(mmean - nmean + 1)
else:
    print(int((mmean - nmean)*2) +1 )

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
d = [list(map(int,input().split())) for i in range(n)]

d = sorted(d,key=lambda x:(x[0],-x[1]))

n_med_min_id = (n+1)//2-1
n_med_min_ab = d[n_med_min_id]
n_med_min_ab_1 = d[n_med_min_id+1]

d = sorted(d,key=lambda x:(-x[1],x[0]))
n_med_max_ab = d[n_med_min_id]
n_med_max_ab_1 = d[n_med_min_id+1]

if n%2==1:
    print(n_med_max_ab[1]-n_med_min_ab[0]+1)
else:
    n_range = (n_med_min_ab[0],n_med_max_ab_1[1])
    n1_range = (n_med_min_ab_1[0],n_med_max_ab[1])
    ret = (n_range[1]+n1_range[1]) - (n_range[0]+n1_range[0]) + 1
    print(ret)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
N, *AB = map(int, read().split())
A,B=AB[::2],AB[1::2]
A.sort()
B.sort(reverse=True)
pos=(N+1)//2-1
if N%2==1:
    ans = B[pos]-A[pos]+1
else:
    ans = (B[pos]+B[pos+1])-(A[pos]+A[pos+1])+1
print(ans)

Submission status: Accepted

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

ans = median(L2) - median(L1)
print(ans+1)

Submission status: Accepted

Solution code:
def E():
    N = int(input())
    pairs = []
    lefts = []
    rights = []
    for _ in range(N):
        pairs.append(list(map(int, input().split())))
        lefts.append(pairs[-1][0])
        rights.append(pairs[-1][1])
    lefts.sort()
    rights.sort()
    if N%2==0:
        print(int(((rights[N//2]+rights[N//2-1])/2+1 - (lefts[N//2]+lefts[N//2-1])/2)*2-1))
        return
    print(rights[(N+1)//2-1] - lefts[(N+1)//2-1] + 1)
E()

Submission status: Accepted

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 == 0:
    med_a = (A[N // 2 - 1] + A[N // 2])
    med_b = (B[N // 2 - 1] + B[N // 2])
else:
    med_a = A[N // 2]
    med_b = B[N // 2]

print(med_b - med_a + 1)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []

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

A.sort()
B.sort()

if N % 2 == 1:
    print(B[N//2] - A[N//2] + 1)
else:
    a0 = A[N//2 - 1]
    b0 = B[N//2 - 1]
    a1 = A[N//2]
    b1 = B[N//2]

    print((b1 + b0) - (a1 + a0) + 1)

Submission status: Accepted

Solution code:
n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(kagen)
zz = sorted(zyogen)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[aa]
    y = zz[aa-1] + zz[aa]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)

Submission status: Accepted

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


def solve(N: int, A: "List[int]", B: "List[int]"):
    left = [A[i] for i in range(N)]
    right = [B[i] for i in range(N)]

    med_left = np.median(left)
    med_right = np.median(right)

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



    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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()
ab.sort(key=itemgetter(0))
if n % 2:
    print(B[n//2] - A[n//2] + 1)
else:
    ans = (B[n//2] + B[n//2 - 1]) - (A[n//2] + A[n//2 - 1]) + 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Zahyou = set()
L = []
R = []
for n in range(N):
    A,B = [int(hoge) for hoge in input().split()]
    L.append(A)
    R.append(B)
L.sort()
R.sort(reverse=True)
if N%2:
    Mid = N//2 + 1
    print(R[Mid-1] - L[Mid-1] + 1)
else:
    ll = N//2
    rr = N//2 + 1
    MidMin = (L[ll-1] + L[rr-1]) /2
    MidMax = (R[ll-1] + R[rr-1]) /2
    print(int((MidMax - MidMin)// 0.5 + 1))

Submission status: Accepted

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()
M=N//2

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

Submission status: Accepted

Solution code:
n = int(input())
ls = [list(map(int, input().split())) for i in range(n)]
ls1=list()
ls2=list()
for i in range(n):
    ls1.append(ls[i][0])
    ls2.append(ls[i][1])
ls1.sort()
ls2.sort()

if n%2:
    print(ls2[n//2]-ls1[n//2]+1)
else:
    a=ls2[n//2-1]+ls2[n//2]
    b=ls1[n//2-1]+ls1[n//2]
    print(a-b+1)

Submission status: Accepted

Solution code:
n=int(input())
AB=[]
A=[]
B=[]
for _ in range(n):
    a,b = map(int,input().split())
    AB.append((a,b))
    A.append(a)
    B.append(b)
A.sort()
B.sort()
#AB = sorted(AB,key=lambda x: x[1])
med = n//2
if n%2 != 0:
    print(B[n//2]-A[n//2]+1)
else:
    p = (A[n//2] + A[n//2-1])
    q = (B[n//2] + B[n//2-1])
    print(q-p+1)

Submission status: Accepted

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


if N%2 == 1:
    lm = sorted(l)[(N+1)//2-1]
    rm = sorted(r)[(N+1)//2-1]
    print(rm - lm + 1)
else:
    lm = sum(sorted(l)[N//2-1:N//2+1])/2
    rm = sum(sorted(r)[N//2-1:N//2+1])/2
    # 0.5 刻みで増えることに注意
    print(int((rm-lm+0.5)*2))

Submission status: Accepted

Solution code:
n=int(input())
AB=[]
A=[]
B=[]
for _ in range(n):
    a,b = map(int,input().split())
    AB.append((a,b))
    A.append(a)
    B.append(b)
A.sort()
B.sort()
#AB = sorted(AB,key=lambda x: x[1])
med = n//2
if n%2 != 0:
    print(B[n//2]-A[n//2]+1)
else:
    p = (A[n//2] + A[n//2-1])/2
    q = (B[n//2] + B[n//2-1])/2
    print(int((q-p)*2+1))