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())
L=[]
for i in range(N):
    a,b=map(int, input().split())
    L.append([a,b])
La=sorted(L)
Lb=sorted(L, key=lambda x: x[1])
if N%2==1:
    
    idx=N//2
    a,b=La[idx]
    Lahalf=L[idx+1:]
    bmin=float("INF")
    for l in Lahalf:
        bmin=min(bmin, l[1])
    MIN1=a
    MIN2=min(b,bmin)

    
    idx=N//2
    a,b=Lb[idx]
    Lbhalf=Lb[:idx]
    amax=0
    for l in Lbhalf:
        amax=max(amax, l[0])
    MAX1=max(a,amax)
    MAX2=b
    #print(MIN1, MIN2, MAX1, MAX2)
    if MIN2<MAX1:
        print(MIN2-MIN1+1+MAX2-MAX1+1)
    else:
        print(MAX2-MIN1+1)
    
else:
    idx=N//2-1
    a,b=La[idx]
    a1,b1=La[idx+1]
    MIN1, MIN2=a,a1

    
    idx=N//2
    a,b=Lb[idx]
    Lbhalf=Lb[:idx]
    _,MAX1=Lb[idx-1]
    MAX2=b
    print(MIN1, MIN2, MAX1, MAX2)
    if MIN2>=MAX1:
        ans=(MAX2-MIN2)*2+1
    else:

        ans=(MIN2-MIN1)*2+1+(MAX2-MAX1)*2+1

    #print(ans)
    #print(MIN1, MIN2, MAX1, MAX2)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [tuple(map(int, input().split())) for _ in range(N)]
if N == 2:
    ans = sorted(X, key=lambda x: x[1], reverse=True)[0][1] - sorted(X, key=lambda x: x[0])[0][0] + 1
else:
    ans = sorted(X, key=lambda x: x[1], reverse=True)[N // 2][1] - sorted(X, key=lambda x: x[0])[N // 2][0] + 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)]
A.sort()
B.sort()
e = int(N/2-1)
f = int(N/2)
g = int((N+1)/2-1)
if N%2 == 0:
  C = (A[e]+A[f])/2
  D = (B[e]+B[f])/2
  print(int(D)-int(C))
else:
  C = A[g]
  D = B[g]
  print(int(D)-int(C))

Submission status: Wrong Answer

Solution code:
import math


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


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

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[]
C=[]
for _ in range(n):
    a,b = map(int,input().split())
    #AB.append((a,b))
    C.append(a)
    C.append(b)
C.sort()
#AB = sorted(AB,key=lambda x: x[1])
med = n//2

if n%2 != 0:
    p,q=C[2*n-n//2-1],C[n//2]
    print(q-p+1)
else:
    p,q,r,s = C[n//2-1],C[n//2],C[2*n-n//2-1],C[2*n-n//2]
    print(int(((s+r)/2 - (p+q)/2)*2 + 1))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())

l = []
r = []

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

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

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

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict

import bisect


#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq


n = readInt()

a0 = [readInts()]


def binary_search(li, index, item):
    low = 0
    high = len(li) - 1

    while low <= high:
        mid = (low + high) //2
        guess = li[mid][index]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return guess


for i in range(n-1):
	a0.append(readInts())

if n%2==1:

	a0.sort(key=lambda x:x[1])
	a1 = a0[:]
	a0.sort()

	x = a1[-1*(n+1)//2][1]
	y = a0[n//2][0]

	print(x-y+1)
else:

	a0.sort(key=lambda x:x[1])
	a1 = a0[:]
	a0.sort()

	x = 1

Submission status: Wrong Answer

Solution code:
def task(n, a, b):
    a.sort()
    b.sort()

    if n % 2 == 0:
        median1 = n // 2
        median2 = n // 2 + 1
        ans1 = a[median1 - 1]
        ans2 = b[median2 - 1]
        print((ans2 - ans1) * 2)
    else:
        median = (n + 1) // 2
        print(b[median - 1] - a[median - 1] + 1)


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

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [[int(i) for i in input().split()] for _ in range(n)]
x.sort(key=lambda x:x[0])
y = sorted(x,key=lambda x:x[1],reverse=True)
if n%2 == 1:
    c = n//2
    if x[c][1] >= y[c][0]:
        ans = y[c][1] - x[c][0] + 1
    else:
        ans = x[c][1] - x[c][0] + y[c][1] - y[c][0] + 2
    print(ans)
else:
    cl = n//2-1
    cr = n//2-1
    lr = x[cl][1]
    rl = y[cr][0]
    print(lr,rl)
    for i in range(n):
        if x[i][0] <= x[cl][0] <= x[i][1]:
            lr = max(lr,x[i][1])
        if x[i][0] <= x[cr][1] <= x[i][1]:
            rl = min(rl, x[i][0])
    print(lr,rl)
    if rl > lr:
        ans = (lr - x[cl][0] + 1)*(y[cr][1]-rl+1)
    else:
        ans = (y[cr][1]-x[cl][0]+1)*(y[cr][1]-x[cl][0])//2
    print(ans)

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:#奇数
    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)/2
    MaxMed = (r_2 + r_1 -2)/2
    print(int((MaxMed - MinMed)//0.5 + 1))

Submission status: Wrong Answer

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

if n%2 == 1:
    m_min = sorted(a)[n//2]
    m_max = sorted(b)[n//2]
    ans = m_max - m_min + 1
if n%2 == 0:
    m_min1 = sorted(a)[n//2 - 1]
    m_min2 = sorted(a)[n//2]
    m_max1 = sorted(b)[n//2 - 1]
    m_max2 = sorted(b)[n//2]
    ans = int(((m_max1 + m_max2)//2 - (m_min1 + m_min2)//2)//0.5) + 1
    if m_min2 == m_max1 or m_min2 == m_max2 or m_min1 == m_max1 or m_min1 == m_max2:
        ans -= 1

print(ans)

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()
amin = min(A)
amax = max(A)
bmin = min(amax,min(B))
bmax = max(B)

if N % 2 == 0:
    ans = 2 * (bmin-amin) + 2 * (bmax-amax)
    print(ans//2+1)
else:
    ans = B[N//2] - A[N//2] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from bisect import bisect_left

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

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

if N%2 == 1:
    # N が奇数のとき
    lm = l[(N+1)//2-1]
    rm = r_list[-((N+1)//2-1)]

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

    lm_h = l[N//2]
    rm_h = r_list[-(N//2-1)]

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

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A,B = [0]*N,[0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    Xmin = min(A)
    Xmax = max(B)
    
    print(int((Xmax-Xmin)*2-1))


main()

Submission status: Wrong Answer

Solution code:
# E

N = int(input())

ab = []

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

ab.sort()
  
import statistics
import math

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

print(am,bm)
if am%0.5 != 0:
  print(bm-am+1)
else:
  print(int(bm-am+2))

Submission status: Wrong Answer

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

if n%2!=0:
    mx = -1
    AB.sort(key=lambda x:x[1], reverse=True)
    for i in range(n//2+1):
        AB[i][2] = 1
        mx = AB[i][1]
    AB.sort(key=lambda x:x[0], reverse=True)
    mn = -1
    cnt = 0
    for i in range(n):
      if AB[i][2]==0:
        mn = AB[i][0]
        cnt += 1
        if cnt==n//2:
          break
    print(mx-mn+1)
else:
    mx = -1
    AB.sort(key=lambda x:x[1], reverse=True)
    for i in range(n//2):
        AB[i][2] = 1
        mx = AB[i][1]
    AB.sort(key=lambda x:x[0], reverse=True)
    mn = -1
    cnt = 0
    for i in range(n):
      if AB[i][2]==0:
        mn = AB[i][0]
        cnt += 1
        if cnt==n//2:
          break
    print((mx-mn)*2+1)

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())
# 　どのx　もその中に持てない区間が何個あるかを累積和で持っておく。
aa, ba, aidx = zip(*sorted(zip(a, b, range(n))))  # aでソート
bb, ab, bidx = zip(*sorted(zip(b, a, range(n))))  # aでソート

if n % 2:
    print(bb[n // 2] - aa[n // 2] + 1)
else:
    if aidx[n // 2 - 1] == bidx[n // 2]:
        ans = 0
        vis = []
        for i in range(aa[n // 2 - 1], bb[n // 2 - 1] + 1):
            for j in range(aa[n // 2], bb[n // 2] + 1):
                if i + j not in vis:
                    ans += 1
                    vis.append(i + j)
    else:
        ans = 0
        vis = []
        for i in range(aa[n // 2 - 1], bb[n // 2 - 1] + 1):
            for j in range(aa[n // 2], bb[n // 2 - 1] + 1):
                if i + j not in vis:
                    ans += 1
                    vis.append(i + j)
    print(ans)

Submission status: Wrong Answer

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

ans=0
if(n%2==0):
    absort=sorted(ab,key=lambda x:x[0])
    ind=(n//2)-1
    a1=absort[ind][0]
    a2=absort[ind+1][0]

    bs=absort[ind:]
    b1=min([bs[i][1] for i in range(len(bs))])

    bs=absort[ind+1:]
    b2=min([bs[i][1] for i in range(len(bs))])

#    print(a1,b1)
#    print(a2,b2)
    ans=(b1+b2)-(a1+a2)+1
    print(ans)

else:
    absort=sorted(ab,key=lambda x:x[0])
    ind=((n+1)//2)-1
    a1=absort[ind][0]

    bs=absort[ind:]
    b1=min([bs[i][1] for i in range(len(bs))])
#    print(a1,b1)

    absort=sorted(ab,key=lambda x:x[1])
    ind=((n+1)//2)-1
    b2=absort[ind][1]

    aas=absort[:ind+1]
    a2=max([aas[i][0] for i in range(len(aas))])
#    print(a2,b2)
    if(a2<=b1):
        ans+=b2-a1+1
    else:
        ans+=b1-a1+1
        ans+=b2-a2+1
    print(ans)

Submission status: Wrong Answer

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])
ls0=ls1+ls2
ls0.sort()
ls1.sort()
ls2.sort()
seg = []
import bisect
for i in range(len(ls0)-1):
    p=[ls0[i],ls0[i+1]]
    low=bisect.bisect_left(ls1,p[0])
    high=n-bisect.bisect_left(ls2,p[1])
    if (low>=n//2 and high>=(n+1)//2):
        seg.append(p)

ans=1
if n%2==0:
    ans+=1
ls1=set(ls1)
ls2=set(ls2)
for i in range(len(seg)):
    if not (seg[i][0] in ls1 and seg[i][1] in ls2):
        continue
    ans+=seg[i][1]-seg[i][0]
print(ans)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
# Count median
N=int(input())
m=[]
M=[]
for i in range(N):
    x,y=map(int,input().split())
    m.append(x)
    M.append(y)
m.sort()
M.sort(reverse=True)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

AB = []

for n in range(N):
  AB.append(list(map(int, input().split())))

index = [AB[i][0] for i in range(len(AB))]
index = np.argsort(index)
AB = list(np.array(AB)[index])

if len(AB)%2==0:
  A = AB[len(AB)//2-1]
  B = AB[len(AB)//2]
  middle = max(B) - min(A)
  print(middle+1)
else:
  C = AB[len(AB)//2]
  print(len(C))

Submission status: Wrong Answer

Solution code:
import math


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


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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    x,y = [int(x) for x in input().split()]
    a.append(x)
    b.append(y)
from collections import Counter
ar = dict(Counter(a))
br = dict(Counter(b))
def judge(k):
    l = 0
    h = 0
    m = 0
    for i in range(n):
        if b[i]<k:
            h+=1
        elif k<a[i]:
            l+=1
        else:
            m+=1
    if n%2!=0:
        if h>n//2 or l>n//2 or m==0:
            return False
        else:
            return True
    else:
        if h>n/2 or l>n/2 or m>=1:
            return False
        else:
            return True

mi = min(a)*2
ma = max(b)*2
while ma-mi>1:
    d = (ma+mi)//2
    if judge(d/2):
        mi = d
    else:
        ma = d
ans = []
ans.append([ma/2,mi/2])
kk = mi
mi = min(a)*2
ma = max(b)*2
while ma-mi>1:
    d = (ma+mi)//2
    if judge(d):
        ma = d
    else:
        mi = d
ans.append([ma/2,mi/2])
kkk = ma - kk + 1
print(kkk)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())

ab_list = []
for i in range(n):
  a, b = list(map(int, input().split()))
  ab_list.append([a,b])
l_ab = sorted(ab_list, key=lambda r: r[0])
h_ab = sorted(ab_list, key=lambda r: r[1])

if n==2:
    center1, center2 = n//2-1, n//2
    
    l_center1_ab, l_center2_ab = l_ab[center1], l_ab[center2]
    left1, right1 = l_center1_ab[0]+l_center2_ab[0], \
        l_center1_ab[1] + l_center2_ab[1]+1
    
    h_center1_ab, h_center2_ab = h_ab[center1], h_ab[center2]
    left2, right2 = h_center1_ab[0] + h_center2_ab[0], \
        h_center1_ab[1]+h_center2_ab[1]+1
# 奇数の場合
elif n%2==1:
    center = n//2
    
    l_center_ab = l_ab[center]
    left1, right1 = l_center_ab[0], \
    	min(l_center_ab[1], l_ab[center+1][1])+1
    
    h_center_ab = h_ab[center]
    left2, right2 = max(h_center_ab[0], h_ab[center+1][0]), \
    	h_center_ab[1]+1
# 偶数の場合
else:
    center1, center2 = n//2-1, n//2
    
    l_center1_ab, l_center2_ab = l_ab[center1], l_ab[center2]
    left1, right1 = l_center1_ab[0]+l_center2_ab[0], \
        min(l_center1_ab[1], l_ab[center2+1][1]) + min(l_center2_ab[1], l_ab[center2+1][1])+1
    
    h_center1_ab, h_center2_ab = h_ab[center1], h_ab[center2]
    left2, right2 = max(h_center1_ab[0], h_ab[center2+1][0]) + max(h_center2_ab[0], h_ab[center2+1][0]), \
        h_center1_ab[1]+h_center2_ab[1]+1
    
print(max(right1, right2) - min(left1, left2))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
  
def main():
    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:
        L = (A[N//2 - 1] + A[N//2])/2
        R = (B[N//2 - 1] + B[N//2])/2
        ans = (R - L + 1) * 2 - 1
    else:
        L = A[N//2]
        R = B[N//2]
        ans = R - L + 1
    print(ans)
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]
    length = []
    for i in range(n):
        length.append(min(r, info[i][1]) - max(l, info[i][0]) + 1)

    length = sorted(length, reverse=True)
    print(length[0] + length[1] - 1)

Submission status: Wrong Answer

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]-AS[N//2-1])+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

nums = [[0, 0] for _ in range(n)]

for i in range(n):
  nums[i][0], nums[i][1] = map(int, input().split())
  
if n % 2 == 0:
  # even
  nums.sort(key=lambda x: x[0])
  a = (nums[(n+1)//2 - 1][0] + nums[(n+1)//2][0])
  nums.sort(key=lambda x: x[1])
  b = (nums[(n+1)//2 - 1][1] + nums[(n+1)//2][1])
  print((b-a) * 2 - 1)
  
else:
  # odd
  nums.sort(key=lambda x: x[0])
  a = nums[(n+1)//2 - 1][0]
  nums.sort(key=lambda x: x[1])
  b = nums[(n+1)//2 - 1][1]
  print(b-a + 1)

Submission status: Wrong Answer

Solution code:
import math
import statistics

ms = set()
for i in range(2,3+1):
    for j in range(3,5+1):
        for k in range(4, 6+1):
            a = sorted([i,j,k])
            m = statistics.median(a) 
            ms.add(m)
print(ms)
print(len(ms))

"""
ms = set()
for i in range(1,2+1):
    for j in range(2,5+1):
        a = sorted([i,j])
        m = statistics.median(a) 
        ms.add(m)
print(ms)
print(len(ms))
"""

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


pool = []
for a,b in ab:
    af = sum([1 for a1,b1 in list(ab) if a1 <= a <= b1])
    bf = sum([1 for a1,b1 in list(ab) if a1 <= b <= b1])
    pool.append((a,af))
    pool.append((b, bf))

# print(pool)

max_pool = max([p[1] for p in pool])

if n%2 == 0:
    # print(pool)
    pool = [p[0] for p in pool if p[1] >= max_pool-1]
    print(max(pool) - min(pool) + 1)
else:
    # print(pool)
    if max_pool%2 == 0:
        pool = [p[0] for p in pool if p[1] >= max_pool]
        print(max(pool) - min(pool) + 1)
    else:
        pool = [p[0] for p in pool if p[1] >= max_pool-1]
        print(max(pool) - min(pool) + 1)

Submission status: Wrong Answer

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

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

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

resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
AB = np.array([list(map(int, input().split())) for i in range(N)])
AB_T = AB.T
A = AB_T[0].tolist()
B = AB_T[1].tolist()
if N == 2:
  X_1 = min(A)
  Y_1 = max(B)
  A.remove(min(A))
  B.remove(max(B))
  X_2 = min(A)
  Y_2 = max(B)
  X = X_2 - X_1
  Y = Y_1 - Y_2 +1
  print(X+Y)
elif N%2 == 0:
  for i in range(int(N//2)):
    A.remove(min(A))
    B.remove(max(B))
    if i == int(N//2)-1:
      print(A)
      print(B)
      X_1 = min(A)
      Y_1 = max(B)
      A.remove(min(A))
      B.remove(max(B))
      X_2 = min(A)
      Y_2 = max(B)
      X = X_2 - X_1
      Y = Y_1 - Y_2 +1
      print(X+Y)
      break
else:
  for i in range(int((N+1)//2)-1):
    A.remove(min(A))
    B.remove(max(B))
    if i == int((N+1)//2)-2:
      L_1 = min(A)
      M_1 = max(B)
      A.remove(min(A))
      B.remove(max(B))
      L_2 = min(A)
      M_2 = max(B)
      L = L_2 - L_1
      M = M_1 - M_2 +1
      print(L+M)
      break

Submission status: Wrong Answer

Solution code:
n = int(input())
import heapq
intervals = []
for i in range(n):
    intervals.append(tuple(map(int, input().split())))

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

if n%2 == 1:
    mid, prev, ne = intervals[((n+1)//2)-1], intervals[(n+1)//2 - 2], intervals[((n+1)//2)]
    # print(mid, prev)

    nm = mid[1] - mid[0] + 1


    if ne[0] < mid[0] and prev[0] < mid[0]:
        nm += (mid[0] - max(ne[0], prev[0]))
    elif ne[0] < mid[0]:
        nm += (mid[0] - ne[0])
    else:
        nm += (mid[0] - prev[0])
    print(nm)

else:
    l, r = intervals[(n//2)-1], intervals[(n//2)]
    # print(l, r)
    d = set()
    for i in l:
        for j in r:
            d.add(i+j)

    print(len(d))

Submission status: Wrong Answer

Solution code:
# E

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

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

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from bisect import bisect_left

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

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

if N%2 == 1:
    # N が奇数のとき
    lm = l[N//2]
    rm = r_list[-N//2]

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

    lm_h = l[N//2]
    rm_h = r_list[-(N//2-1)]

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0 for _ in range(N)]

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
left = []
right = []
for _ in range(N):
    l, r = map(int, input().split())
    left.append(l)
    right.append(r)
left.sort()
right.sort()
if N%2==0:
    for i, (l, r) in enumerate(zip(left, right[1:]), 1):
        if i==N//2:
            print((r-l)*2-1)
else:
    for i, (l, r) in enumerate(zip(left, right[1:]), 1):
        if i==N//2:
            print(r-l+1)

Submission status: Wrong Answer

Solution code:
import math


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


N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
x = median(A)
y = median(B)
if N % 2:
    print(y - x + 1)
else:
    print(math.ceil(y) - math.floor(x) + 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)
if N%2==0:
  A.sort()
  B.sort()
  c=int(N/2)
  d=A[c-1]+B[c-1]
  e=A[c]+B[c]
  f=e-d
  print(f+1)
else:
  A.sort()
  B.sort()
  c=int(N/2)
  print(B[c]-A[c]+1)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n)]

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