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:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    ab = [list(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.sort()
    b.sort()
    if n % 2 == 0:
        print(b[n // 2 - 1] + b[n // 2] - a[n // 2 - 1] - a[n // 2]+1)
    else:
        print(b[n//2]-a[n//2]+1)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import statistics
import math

N = int(input())

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

AM = statistics.median(A)
BM = statistics.median(B)
if N % 2 == 1:
    ANS = (BM - AM) + 1
else:
    ANS = int((BM - AM) * 2 + 1)
print(ANS)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
    tmp = input().split()
    a.append(int(tmp[0]))
    b.append(int(tmp[1]))
a_sorted = sorted(a)
b_sorted = sorted(b)

if n % 2 == 1:
    ans = b_sorted[(n-1)//2] - a_sorted[(n-1)//2] + 1
else:
    ans = (b_sorted[n//2-1] + b_sorted[n//2]) - (a_sorted[n//2-1] + a_sorted[n//2]) + 1
print(ans)

Submission status: Accepted

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:
      l=mid
    elif 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:
      l=mid
    elif cnt2>n//2-1:
      r=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:
      l=mid
    elif 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:
      l=mid
    elif cnt2>n//2:
      r=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:
      l=mid
    elif 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:
      l=mid
    elif cnt2>n//2:
      r=mid
    else:
      r=mid
  l2=l
  r2=r
  print(l1-r2+1)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

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

AB = np.array(AB)

A = AB[:,0]
B = AB[:,1]

m_min = np.median(A)
m_max = np.median(B)

if N%2==0:
    ans = (int(m_max*10) - int(m_min*10)) //5 +1
else:
    ans = int(m_max) - int(m_min) + 1

print(ans)

Submission status: Accepted

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

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

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

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

A.sort()
B.sort()

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    A = []
    B = []
    for _ in range(N):
        a,b = LI()
        A.append(a)
        B.append(b)

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

    if N % 2:
        i = A[N//2]
        j = B[N//2]
        print(j-i+1)
    else:
        i1 = A[N//2-1]
        i2 = A[N//2]
        j1 = B[N//2-1]
        j2 = B[N//2]

        x1 = j1 - i1
        x2 = j2 - i2
        ans = x1 + x2 + 1
        print(ans)


if __name__ == '__main__':
    main()

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(reverse=True)
if n % 2 == 1:
    mn = A[(n+1)//2-1] 
    mx = B[(n+1)//2-1]
    print(mx - mn + 1)
else:
    mn1 = A[(n+1)//2-1]
    mn2 = A[(n+1)//2]    
    mx1 = B[(n+1)//2]    
    mx2 = B[(n+1)//2-1]
    # print(mn1,mx1,mn2,mx2)
    print((mx2+mx1)-(mn1+mn2)+1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
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(int(((B[N//2]+B[N//2-1])/2 - (A[N//2]+A[N//2-1])/2)*2 + 1))
else:
    print(B[N//2] - A[N//2] + 1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import statistics
import math

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

arr = np.array(l)

arr1 = arr[:,:1].tolist()
arr2 = arr[:,1:].tolist()

l1 = list(itertools.chain.from_iterable(arr1))
l2 = list(itertools.chain.from_iterable(arr2))

a = statistics.median(l1)
b = statistics.median(l2)

if n%2 ==1:
    print(b-a+1)
else:
    print(int((b-a)//0.5) + 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()
if N%2 == 0:
    n = N//2
    MIN = (A[n-1] + A[n])/2
    MAX = (B[n-1] + B[n])/2
    print(int(2*(MAX-MIN)+1))
else:
    n = N//2
    MIN = A[n]
    MAX = B[n]
    print(MAX-MIN+1)

Submission status: Accepted

Solution code:
n = int(input())

min = []
max = []

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

min.sort()
max.sort()

if n % 2 == 0:
    bot1 = min[int(n/2)-1]
    bot2 = min[int(n/2)]
    top1 = max[int(n/2)-1]
    top2 = max[int(n/2)]
    ans = (top1 + top2) - (bot1 + bot2) + 1



else:
    bot = min[int((n-1)/2)]
    top = max[int((n-1)/2)]
    ans = top - bot + 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

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

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
X = []
for i in range(N):
    X.append(list(map(int,input().split())))
temp = np.median(X,axis=0)
if N % 2 == 1:
    print(int(temp[1]-temp[0]+1))
else:
    print(int(2*temp[1]-2*temp[0]+1))

Submission status: Accepted

Solution code:
N=int(input())

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

if N%2==1:
    print(M[N//2]-m[N//2]+1)
else:
    M1=(M[N//2-1]+M[N//2])/2
    m1=(m[N//2-1]+m[N//2])/2
    print(int((M1-m1)*2+1))

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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


from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret


def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while (True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret


def solve():
    n = getN()
    nums = []
    for i in range(n):
        nums.append(getList())

    if n % 2 == 1:
        nums.sort()
        med = nums[(n + 1) // 2 - 1][0]
        nums.sort(key=lambda x: x[1])
        medhigh = nums[(n + 1) // 2 - 1][1]

        print(medhigh - med + 1)
    else:
        nums.sort()
        med = (nums[n // 2 - 1][0] + nums[n // 2][0]) / 2
        nums.sort(key=lambda x: x[1])
        medhigh = (nums[n // 2 - 1][1] + nums[n // 2][1]) / 2
        # print(medhigh, med)
        print(int((medhigh - med) * 2) + 1)


def main():
    # n = getN()
    # for _ in range(n):
    solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

if N%2 == 1:
  AB.sort(key=lambda x:x[1])
  Mmax = AB[N//2][1]
  AB.sort()
  Mmin = AB[N//2][0]
  nowB = 0
  empty = 0
  for A, B in AB:
    if A <= Mmin:
      nowB = max(nowB, B)
    else:
      if nowB >= Mmax:
        break
      if A > nowB+1:
        empty += (min(A,Mmax+1) -nowB -1)
      nowB = B
  print(Mmax -(Mmin-1) -empty)
else:
  AB.sort(key=lambda x:x[1])
  Mmax = (AB[N//2-1][1] + AB[N//2][1])
  AB.sort()
  Mmin = (AB[N//2-1][0] + AB[N//2][0])
  nowB = 0
  empty = 0
  for A, B in AB:
    if A <= Mmin:
      nowB = max(nowB, B)
    else:
      if nowB >= Mmax:
        break
      if A > nowB+1:
        empty += (min(A,Mmax+1) -nowB -1)
      nowB = B
  print(Mmax -(Mmin-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:
    m = n//2
    c = (b[m-1]+b[m])-(a[m-1]+a[m])
else:
    m = n//2+1
    c = b[m-1]-a[m-1]
print(c+1)

Submission status: Accepted

Solution code:
n = int(input())

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

a.sort()
b.sort()

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

Submission status: Accepted

Solution code:
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
# AB = np.array([np.array(input().split(), np.int)
AB = np.array(AB)
# tAB = list(zip(*AB))
# print(AB)
tAB = AB.T
# print(tAB)
# print()
A = tAB[0]
B = tAB[1]
A.sort()
B.sort()

# print(A, B)

if N%2 == 0:
    midA1 = A[N//2-1]
    midA2 = A[N//2]
    midB1 = B[N//2-1]
    midB2 = B[N//2]

    midmidA = (midA1+midA2)/2
    midmidB = (midB1+midB2)/2
    res = int((midmidB-midmidA)/(0.5) + 1)
    print(res)

    # d = defaultdict(int)

    # for val1 in range(midA1, midB1+1):
    #     for val2 in range(midA2, midB2+1):
    #         val = (val1 + val2)/2
            # d[val] += 1
    # print(len(d.keys()))
    
else:
    midA = A[N//2]
    midB = B[N//2]
    print(midB-midA+1)

Submission status: Accepted

Solution code:
n=int(input())

ll=[]
rr=[]

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

ll.sort()
rr.sort()

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

Submission status: Accepted

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

value = set()

for i in range(N):
    a, b = I[i]
    value.add(a)
    value.add(b)
value = list(value)
value.sort()
comp = {v : k for k, v in enumerate(value)}


M = len(value)

arr1 = [0 for _ in range(M)]
arr2 = [0 for _ in range(M)]

for i in range(N):
    a, b = I[i]
    arr1[comp[a]] += 1
    arr2[comp[b]] += 1

for i in range(M - 1):
    arr1[i + 1] += arr1[i]
    arr2[M - i - 2] += arr2[M - i - 1]


if N % 2 == 1:
    lt = 0
    rt = M - 1
    for i in range(M):
        if arr1[i] >= (N + 1)//2:
            lt = i
            break
    for i in range(M)[::-1]:
        if arr2[i] >= (N + 1)//2:
            rt = i
            break
    print(value[rt] - value[lt] + 1)

else:
    lt = 0
    rt = M - 1
    mlt = 0
    mrt = M - 1
    for i in range(M):
        if arr1[i] >= N//2:
            lt = i
            break
    for i in range(M):
        if arr1[i] >= N//2 + 1:
            mlt = i
            break
    for i in range(M)[::-1]:
        if arr2[i] >= N//2:
            rt = i
            break
    for i in range(M)[::-1]:
        if arr2[i] >= N//2 + 1:
            mrt = i
            break
    l = value[lt]
    r = value[rt]
    ml = value[mlt]
    mr = value[mrt]

    print(r + mr - l - ml + 1)

Submission status: Accepted

Solution code:
def median(a, n):
    if n % 2:
        return a[n // 2]
    return (a[n // 2 - 1] + a[n // 2]) / 2
n = int(input())
l,r = [], []
for _ in range(n):
    a,b = map(int, input().split())
    l.append(a)
    r.append(b)
l = sorted(l)
r = sorted(r)
left,right = median(l, n), median(r, n)
if n % 2:
    print(right - left + 1)
else:
    print(int(2 * (right - left) + 1))

Submission status: Accepted

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

import sys
import collections
import numpy as np
input = sys.stdin.readline
n = int(input())

A =np.array([list(map(int,input().split())) for i in range(n)])
B = np.sort(A, axis=0)

if n %2 ==1:
    print(B[((n+1)//2)-1][1] - B[((n+1)//2)-1][0] +1)
    sys.exit()
else:
    mn = (B[n//2][0] + B[(n-1)//2][0] )/2
    mx = (B[n//2][1] + B[(n-1)//2][1] )/2
    print(int(((mx - mn) *2) +1))
    sys.exit()

Submission status: Accepted

Solution code:
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = []
    B = []
    for _ in range(N):
        a, b = LI()
        A.append(a)
        B.append(b)

    A.sort()
    B.sort()

    A_med = 0
    B_med = 0
    if N%2==0:
        A_med_2 = (A[N//2-1] + A[N//2])
        B_med_2 = (B[N//2-1] + B[N//2])
        print((B_med_2-A_med_2)+1)
    else:
        A_med_2 = A[(N+1)//2-1]*2
        B_med_2 = B[(N+1)//2-1]*2
        print((B_med_2-A_med_2)//2+1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = []
b = []

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

med_a = statistics.median(a)
med_b = statistics.median(b)

if n % 2 == 1:
    print(abs(med_b - med_a) + 1)
if n % 2 == 0:
    print(int(abs(2 * med_b - 2 * med_a) + 1))

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

n = int(input())
aa = [None] * n
bb = [None] * n
for i in range(n):
    a, b = map(int, input().split())
    aa[i] = a
    bb[i] = b

def median(arr):
    if len(arr) % 2 == 0:
        return (arr[n // 2 - 1] + arr[n // 2]) / 2
    else:
        return arr[n // 2]

m = n
if n % 2 == 0:
    m *= 2
medmin = median(sorted(map(lambda x: x * m, aa)))
medmax = median(sorted(map(lambda x: x * m, bb)))

print(int((medmax - medmin) / n) + 1)

Submission status: Accepted

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

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

print((b - a) // 2 + 1 if N % 2 == 1 else b - a + 1)

Submission status: Accepted

Solution code:
N = int(input())

XA = []
XB = []
for i in range(N):
    A, B = (int(i) for i in input().split())
    XA.append(A)
    XB.append(B)

XA.sort()
XB.sort()

if N % 2 == 1:
    aa = XA[ (N - 1) // 2] 
    bb = XB[ (N - 1) // 2]
    print(bb - aa + 1)
else:
    aa1 = XA[N // 2]
    bb1 = XB[N // 2]
    aa = XA[N // 2 - 1]
    bb = XB[N // 2 - 1]
    print((bb1 + bb) - (aa1 + aa) + 1)

Submission status: Accepted

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

N = len(alist)
alist.sort()
blist.sort()
# 偶数の場合
if N % 2 == 0:
    median1 = N/2
    median2 = N/2 + 1
    median1 = int(median1) - 1
    median2 = int(median2) - 1
    amedian = (alist[median1] + alist[median2]) / 2
    bmedian = (blist[median1] + blist[median2]) / 2
    ans = (bmedian-amedian)*2+1
# 奇数の場合
else:
    median = (N + 1) / 2
    median = int(median) - 1
    amedian = alist[median]
    bmedian = blist[median]
    ans = bmedian-amedian+1
print(int(ans))

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))


n = ii()
A = []
B = []

for _ in range(n):
    a,b = iim()
    A.append(a)
    B.append(b)
A.sort()
B.sort()

if n%2 == 1:
    ans = B[n//2]-A[n//2]+1
else:
    lmin = A[n//2-1]
    lmax = B[n//2-1]
    rmin = A[n//2]
    rmax = B[n//2]
    ans = (rmax+lmax) - (rmin+lmin) + 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys, random, math
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def main():
    inf = 10 ** 20

#    t = int(input())
#    t, a, b = map(int, input().split())
    t = 1
    
    for _ in range(1, t+1):
    #    print("Case #{}: ".format(_), end = '')
        
        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>>1)] - a[(n>>1)] + 1)
        else:
            l2, r2 = a[(n>>1)], b[(n>>1)]
            l1, r1 = a[(n>>1)-1], b[(n>>1)-1]
            
            print((r2-l2+1)+(r1-l1))
        
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
AB = []
A = []
B = []
for _ in range(n):
    a, b = Is()
    A.append(a)
    B.append(b)
    AB.append((a, b))
A.sort()
B.sort()
if n % 2 == 1:
    print(B[n//2]-A[n//2]+1)
    exit()
l = (A[n//2-1]+A[n//2])/2
r = (B[n//2-1]+B[n//2])/2
print(int((r-l)*2+1))

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
#a=input_list()
#a=input().split()
#n=int(a[0])
#m=float(a[1])
#print(math.floor(n*m))
s=[]
e=[]
for _ in range(n):
    tmp=input_list()
    s.append(tmp[0])
    e.append(tmp[1])

s.sort()
e.sort()
if n%2==1:
    num=(n-1)//2
    ans=e[num]-s[num]+1
else:
    num=n//2
    st=s[num]+s[num-1]
    en=e[num]+e[num-1]
    ans=en-st+1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort()
if N%2 == 1:
    mini = L[N//2][0]
    L.sort(reverse=True, key=itemgetter(1))
    maxi = L[N//2][1]
    ans = maxi-mini+1
else:
    mini = (L[N//2][0]+L[N//2-1][0])
    L.sort(reverse=True, key=itemgetter(1))
    maxi = (L[N//2][1]+L[N//2-1][1])
    ans = maxi-mini+1

print(ans)

Submission status: Accepted

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:
  first = (start[int(N/2)-1] + start[int(N/2)]) / 2
  last = (end[int(N/2)-1] + end[int(N/2)]) / 2
  print(int((last - first)*2 + 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

a = []
b = []

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

a_sort = sorted(a)
b_sort = sorted(b)

flags = [False] * n

s = 0

if n % 2 == 1:
    s = b_sort[n//2] - a_sort[n//2] + 1

else:
    p_min = a_sort[(n//2)-1]
    p_max = b_sort[(n//2)-1]
    q_min = a_sort[(n//2)]
    q_max = b_sort[(n//2)]

    s = ((p_max+q_max) - (p_min+q_min) ) + 1
print(s)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
AB = [LI() for _ in range(N)]
AB_a = sorted(AB,key=lambda x: x[0])
AB_b = sorted(AB,key=lambda x: x[1])

#"""
if N%2 == 0:
    p = N//2 -1
    q = p+1
    #print(p,q)
    ans = abs(AB_a[p][0]+AB_a[q][0] - AB_b[p][1]-AB_b[q][1])+1    
else:
    p = (N+1)//2 -1
    #print(p)
    ans = abs(AB_a[p][0] - AB_b[p][1])+1
print(ans)
#"""

Submission status: Accepted

Solution code:
import statistics

n = int(input())
ab = [list(map(float, input().split())) for _ in range(n)]
a = []
b = []
for i in ab:
    a.append(i[0])
    b.append(i[1])
# print(a)
# print(b)

min_median = statistics.median(a)
max_median = statistics.median(b)
# print(min_median)
# print(max_median)
c = max_median-min_median
if n%2 ==0:
    ans = int(c*2)
else:
    ans = int(c)
print(ans+1)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
    _A,_B=[int(i) for i in input().split(" ")]
    A.append(_A)
    B.append(_B)

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

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

Submission status: Accepted

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

A.sort()
B.sort()

if N % 2 > 0:
  print(abs(B[(N-1) // 2] - A[(N-1) // 2]) + 1)
else:
  B1,B2 = B[N//2-1], B[N//2]
  A1,A2 = A[N//2-1], A[N//2]
  xb, xa = (B1+B2)/2, (A1+A2)/2
  print(int((xb-xa) * 2) + 1)

Submission status: Accepted

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]+b[(n-1)//2])-(a[n//2]+a[(n-1)//2]))

Submission status: Accepted

Solution code:
n=int(input())

minl=[]
maxl=[]
for i in range(n):
  k=input().split()
  minl.append(int(k[0]))
  maxl.append(int(k[1]))
  
minl.sort()
maxl.sort()

if n%2==1:
  c=int((n+1)/2)-1
  re=maxl[c]-minl[c]+1
else:
  c2=int(n/2)
  c1=c2-1
  re=(maxl[c1]+maxl[c2])-(minl[c1]+minl[c2])+1
  
print(re)

Submission status: Accepted

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

S.sort()
E.sort()

if N % 2 == 0:
    mi = S[N//2-1][0] + S[N//2][0]
    ma = E[N//2-1][0] + E[N//2][0]
    print(ma-mi+1)
else:
    mi = S[(N+1)//2-1][0]
    ma = E[(N+1)//2-1][0]
    print(ma-mi+1)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
AB = [LI() for i in range(N)]
A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]
A = sorted(A)
B = sorted(B)

from copy import deepcopy

if N % 2 == 0:
    C = [0]*N
    D = [0]*N
    for i in range(N):
        C[i] = 2*A[i]
        D[i] = 2*B[i]
    m = N//2
    d = (D[m]+D[m-1])//2
    c = (C[m]+C[m-1])//2
    print(d-c+1)
    exit()

n = N//2
print(B[n]-A[n]+1)