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:
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 = []
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 ] - A[ i2 ] ) * ( B[ i1 ] - A[ i1 ] ) )
else:
  i = ( n + 1 ) // 2 - 1
  print( B[ i ] - A[ i ] + 1 )

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
B = []
for _ in range(N):
    a, b = [int(_) for _ in 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:
    sa, ea = A[N//2 - 1], A[N//2]
    sb, eb = B[N//2 - 1], B[N//2]
    print(eb+ea - (sa+sb) + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort()
if N % 2 == 1:
    print(arr[N//2][1]-arr[N//2][0]+1)
else:
    if arr[(N//2)-1][1] < arr[N//2][0]:
        print(arr[(N//2)-1][1] - arr[(N//2)-1][0] + arr[N//2][1] - arr[N//2][0])
    else:
        print(arr[N//2][1]-arr[(N//2)-1][0]+1)

Submission status: Wrong Answer

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
    # print(B1, B2, A1, A2, ans)
    # if ans % 1 != 0:
    #     ans = int(ans*2)
else:
    mid = (N+1)//2-1
    A1,B1 = sortA[mid]
    A2,B2 = sortB[mid]
    # print(A1, A1, B1, B2)
    ans = min(B1, B2) - max(A1, A2) + 1
print(int(ans))

Submission status: Wrong Answer

Solution code:
import statistics
n=int(input())
r=set([])
x=[[]]*n
for i in range(n):
  a,b=list(map(int,input().split()))
  x[i]=[a,b]
r0=statistics.median([x[z][0] for z in range(n)])
r1=statistics.median([x[z][1] for z in range(n)])
if ((r0*2) % 2)>0 and ((r1*2) % 2)>0:
  mult=2
else:
  mult=1
#print(r0)
#print(r1)
mult=int((r1-r0)*mult+1)
print(mult)
  #r=r|

Submission status: Wrong Answer

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

if n % 2 == 0:
  a_mid = al[n//2-1]
  b_mid = bl[n//2]
  print((b_mid - a_mid) * 2 - 1)  
else:
  a_mid = al[(n+1)//2-1]
  b_mid = bl[(n+1)//2-1]
  print(b_mid - a_mid + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

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

    L = list(zip(*sorted(list(zip(*L)))))
    if N % 2 == 0:
        M = (L[N//2][1]+L[N//2-1][1])/2
        m = (L[N//2][0]+L[N//2-1][0])/2
        if L[N//2][0] == L[N//2-1][0]:
            v = L[N//2][0]
            mval = 10**10
            Mval = -1
            for i in L:
                if i[0] == v:
                    mval = min(i[1], mval)
                    Mval = max(i[1], Mval)
            M = (mval+Mval)/2
            m = v
        print(int((M-m)//0.5+1))
    else:
        M = L[N//2][1]
        m = L[N//2][0]
        print(int(M-m+1))


resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
AB = li2(N)
A = [0]*N
B = [0]*N
for i in range(N):
    A[i] = AB[i][0]
    B[i] = AB[i][1]

if N%2:
    num_a = sorted(A)[N//2]
    num_b = sorted(B)[N//2]
    print(num_b-num_a+1)
else:
    A = sorted(A)
    B = sorted(B)
    min_a = A[N//2-1]
    max_a = A[N//2]
    min_b = B[N//2-1]
    max_b = B[N//2]
    #print(max(max_b, )-min(min_a, min_b)+1)
    print(max_b+max_a-(min_b+min_a)+1)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A = []
B = []
ans = 0

for i in range(N):
    AB = input().split()
    A.append(int(AB[0]))
    B.append(int(AB[1]))

if(N%2==0):
    if(N ==2):
        ans = (max(B)+min(B))-(max(A)+min(A))+1
    else:
        A.remove(min(A))
        B.remove(max(B))
        ans = (max(B)+min(B))-(max(A)+min(A))+1
else:
    A.remove(min(A))
    B.remove(max(B))
    ans = max(B)-min(A)+1

print(ans)

Submission status: Wrong Answer

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

N = int(input())
A = []
B = []
for _ in range(N):
    ab = list(map(int, input().split()))
    A.append(ab[0])
    B.append(ab[1])

A.sort()
B.sort()

if N % 2 == 0:
    idx1 = N//2-1
    idx2 = N//2

    mn1, mn2 = A[idx1], A[idx2]
    mx1, mx2 = B[idx1], B[idx2]

    cmn = mx1-mn2 + 1
    btm = mn2-mn1
    up  = mx2-mx1
    g1 =  mx1-mn1+1
    g2 =  mx2-mn2+1

    print( cmn*(cmn+1)//2 + 1 + 1 )
else:
    idx = N//2
    print( B[idx] - A[idx] + 1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
ABs_desc = deepcopy(ABs)

ABs.sort(key=lambda x:(x[0],-x[1]))
ABs_desc.sort(key=lambda x: (-x[1],x[0]))

if N%2:
    for AB in ABs:
        if AB[0] == ABs[N//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[N//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    print(B2-A1+1)
else:
    for AB in ABs:
        if AB[0] == ABs[(N-1)//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[(N-1)//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    print(B1+B2-A1-A2+1)

Submission status: Wrong Answer

Solution code:
import statistics
n = int(input())
a_list = [0 for i in range(n)]
b_list = [0 for i in range(n)]
x_list = [(0,0) for i in range(n)]

for i in range(n):
  a,b = map(int,input().split())
  a_list[i] = a
  b_list[i] = b
  x_list[i] = (a,b)
  
a_sort = sorted(a_list)
b_sort = sorted(b_list)


if n%2 == 1:
  a_med = statistics.median(a_list)
  b_med = statistics.median(b_list)
  print(b_med-a_med+1)
  
else:
  a_med = statistics.median_low(a_list)
  b_med = statistics.median_high(b_list)
  print(int(((b_med-a_med+1)*(b_med-a_med))/2))

Submission status: Wrong Answer

Solution code:
N = int(input())

if N%2 == 1:

    ab = []

    for i in range(N):
        a,b = map(int,input().split())
        m = (a+b)//2

        ab.append((m,a,b))
    
    ab.sort()

    l = ab[(N-1)//2]
    print(l[2]-l[1]+1)

else:
    ab = []
    for i in range(N):
        a,b = map(int,input().split())
        m = (a+b)//2
        ab.append((m,a,b))

    ab.sort()
    l1 = ab[N//2-1]
    l2 = ab[N//2]

    l = l1[1]
    r = l2[2]


    for _,a,b in ab:

        if a <= l and b >= r:
            r = b
            l = a
    print(r-l+1)

Submission status: Wrong Answer

Solution code:
min_li, max_li = [], []
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    min_li.append((a, b))
    max_li.append((a, b))
min_li.sort()
max_li.sort(key=lambda x: x[1], reverse=True)
if n % 2 == 1:
    mid = n // 2
    blue_min = min_li[mid][0]
    blue_max = min(min_li[mid:], key=lambda x: x[1])[1]
    red_max = max_li[mid][1]
    red_min = max(max_li[mid:])[0]
else:
    mid_1 = n // 2 - 1
    mid_2 = n // 2
    min_li_half = sorted(min_li[mid_1:], key=lambda x: x[1])
    blue_min = min_li[mid_1][0] + min_li[mid_2][0]
    blue_max = min_li_half[0][1] + min_li_half[1][1]
    max_li_half = sorted(max_li[mid_1:], reverse=True)
    red_max = max_li[mid_1][1] + max_li[mid_2][1]
    red_min = max_li_half[0][0] + max_li_half[1][0]

if blue_max >= red_min:
    ans = red_max - blue_min + 1
else:
    ans = blue_max - blue_min + red_max - red_min + 2
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import statistics

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

a_med = statistics.median(a)
b_med = statistics.median(b)
if len(a) % 2 == 0:
    print(int(b_med - a_med + 2))
else:
    print(b_med - a_med + 1)

Submission status: Wrong Answer

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

ab.sort()
ba.sort(reverse=True)

ans = 0
if n%2 == 1: # nが奇数
    left = ab[n//2][0]
    right_end = ba[n//2][0]
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans += (right-left)+1 * 0
else: # nが偶数
    # まずn//2番目の値の範囲
    ans0 = 0
    left_end = ab[n//2-1][0]
    right_end = ba[n//2][0]
    left = left_end
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans0 += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans0 += (right-left)+1
    left_end0 = left_end
    right_end0 = right_end
    # 次に(n//2+1)番目の値の範囲
    ans1 = 0
    left_end = ab[n//2][0]
    right_end = ba[n//2-1][0]
    left = left_end
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans1 += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans1 += (right-left)+1
    left_end1 = left_end
    right_end1 = right_end
    # print(left_end0,right_end0,left_end1,right_end1)
    ans = (((right_end1+right_end0)//2) - ((left_end1+left_end0)//2))*2 + 1

print(ans)

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 = intervals[((n+1)//2)-1], intervals[(n+1)//2 - 2]
    # print(mid, prev)

    nm = mid[1] - mid[0] + 1
    print(nm)
    # if prev[0] < mid[0]:
    #     print(nm)
    # else:
        # print(mid[1] - prev[0] + 1)

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





# print(intervals)

Submission status: Wrong Answer

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

lp = sorted(l, key = lambda x:x[0])
fir = lp[(N-1)//2][0]
lm = sorted(l, key= lambda x:x[0], reverse = True)
fim = lm[(N-1)//2][-1]
print(abs(fir-fim)+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:
  print((max[n//2] + max[n//2 - 1]) -(min[n//2] + min[n//2 - 1])+ 1)
else:
  print(max[n//2]-min[n//2]+1)
print(min)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N = int(input())
    B = []
    A = []
    for _ in range(N):
        a, b = [int(x) for x in input().split(" ")]
        A.append(a)
        B.append(b)

    A.sort()
    B.sort()
    assert len(A) == N
    assert len(B) == N
    if N % 2 == 0:
        start = A[(N // 2) - 1]
        end = B[(N // 2)]

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

        print(end - start + 1)

Submission status: Wrong Answer

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))
 
def main():
    import sys
    input=sys.stdin.readline
    n=I()
    a=[]
    b=[]
    for i in range(n):
        ai,bi=L()
        a.append(ai)
        b.append(bi)
    media=0
    medib=0
    odd=False if n%2==0 else True
    a.sort()
    b.sort()
    ans=0
    if odd:
        media=a[(n+1)//2-1]
        medib=b[(n+1)//2-1]
        ans=int(medib-media)+1
    else:
        media=(a[n//2-1]+a[n//2])/2
        medib=(b[n//2-1]+b[n//2])/2
        ans=int(medib-media)+2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ab.sort()
ba.sort(reverse=True)

ans = 0
if n%2 == 1: # nが奇数
    left = ab[n//2][0]
    right_end = ba[n//2][0]
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans += (right-left)+1
else: # nが偶数
    # まずn//2番目の値の範囲
    ans0 = 0
    left_end = ab[n//2-1][0]
    right_end = ba[n//2][0]
    left = left_end
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans0 += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans0 += (right-left)+1
    left_end0 = left_end
    right_end0 = right_end
    # 次に(n//2+1)番目の値の範囲
    ans1 = 0
    left_end = ab[n//2][0]
    right_end = ba[n//2-1][0]
    left = left_end
    right = min(ab[n//2][1], right_end)
    for i in range(n//2+1,n):
        if right >= ab[i][0]: # 右端が次の左端より大きい
            right = min( max(right, ab[i][1]), right_end ) # 次の領域につなげる
        elif ab[i][0] < right_end: # 右端が次の左端より小さい＆まだ領域がある
            ans1 += (right-left)+1 # 一旦切れる
            left = ab[i][0]
            right = min( ab[i][1], right_end )
        else: # 終了
            break
    ans1 += (right-left)+1
    left_end1 = left_end
    right_end1 = right_end
    # print(left_end0,right_end0,left_end1,right_end1)
    ans = (((right_end1+right_end0)//2) - ((left_end1+left_end0)//2))*2 + 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = [0]*(n+1)
b = [0]*(n+1)
for i in range(1,n+1):
    aa, bb = MAP()
    a[i] = aa
    b[i] = bb

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

print(res)

Submission status: Wrong Answer

Solution code:
import statistics
n=int(input())
r=set([])
x=[[]]*n
for i in range(n):
  a,b=list(map(int,input().split()))
  x[i]=[a,b]
r0=statistics.median([x[z][0] for z in range(n)])
r1=statistics.median([x[z][1] for z in range(n)])
if ((r1*2) % 2)>0:
  mult=2
else:
  mult=1
#print(r0)
#print(r1)
mult=int((r1-r0)+mult)
print(mult)
  #r=r|

Submission status: Wrong Answer

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

result=0
mid_list=[]
if N % 2 != 0: #奇数
    mid = int((N+1)/2 -1)
    result = B[mid]-A[mid]+1
else: #偶数
    mid1 = int(N/2 - 1)
    mid2 = int(N/2)

    for i in range(A[mid1],B[mid1]+1):
        for j in range(A[mid2],B[mid2]+1):
            if i <= j:
                if (i+j)/2 not in mid_list:
                    result += 1
                    mid_list.append((i+j)/2)

print(result)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
if N%2==0:
    l=[]
    for a,b in zip(A,B):
        l.append((a,b))
    sa=list(sorted(l,key=lambda t:(t[0],t[1])))
    l.remove(sa[N//2-1])
    sb=list(sorted(l,key=lambda t:(t[1],t[0])))
    ll=sa[N//2-1][0]
    lr=sa[N//2-1][1]
    rl=sb[N//2-1][0]
    rr=sb[N//2-1][1]
    if N//2+1<=N-2:
        lr=min(lr,sb[N//2+1][1])
    if N//2-2>=0:
        rl=max(rl,sa[N//2-2][0])
    ans=0
    ans+=rr-rl+1
    ans+=lr-ll
    print(ans)
else:
    if N==1:
        print(B[0]-A[0]+1)
    else:
        u=list(set(A+B))
        u.sort()
        d={x:i for i,x in enumerate(u)}
        aa=[d[x] for x in A]
        bb=[d[x] for x in B]
        l=[]
        for a,b in zip(aa,bb):
            l.append((a,b))
        aa.sort()
        bb.sort()
        left=aa[N//2-1]
        right=bb[N//2+1]
        class RangeBIT:
            def __init__(self,n):
                self.p=self.BIT(n+1)
                self.q=self.BIT(n+1)
            
            def add(self,s,t,x):
                self.p.add(s,-x*s)
                self.p.add(t,x*t)
                self.q.add(s,x)
                self.q.add(t,-x)
            
            def sum(self,s,t):
                return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
            
            class BIT:
                def __init__(self,n):
                    self.num=n
                    self.dat=[0]*(self.num+1)
                
                def add(self,i,x):
                    i+=1
                    while i<=self.num:
                        self.dat[i]+=x
                        i+=i&-i
                
                def sum(self,i):
                    i+=1
                    s=0
                    while i>0:
                        s+=self.dat[i]
                        i-=i&-i
                    return s
        bit=RangeBIT(len(u))
        for a,b in l:
            if left==a:
                lleft=aa[N//2]
            else:
                lleft=left
            if right==b:
                rright=bb[N//2]
            else:
                rright=right
            a=max(lleft,a)
            b=min(rright,b)
            if a<=b:
                bit.add(a,b+1,1)
        ans=0
        tmp=-1
        for i in range(len(u)):
            if bit.sum(i,i+1):
                if tmp==-1:
                    tmp=i
            else:
                if tmp>=0:
                    ans+=u[i-1]-u[tmp]+1
                    tmp=-1
        print(ans)

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,collections as cl,bisect as bs,heapq as hq

sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()
po = []
no = [0 for i in range(n)]
co = 0
ans = 0
pre = 0
pr = -1
if n % 2 != 0:
	for i in range(n):
		a,b = m()
		hq.heappush(po,[a,i])
		hq.heappush(po,[b,i])
	while len(po) != 0:
		kkk = hq.heappop(po)
		if co == (n // 2)+1:
			if pre != pr:
				ans += 1
			ans += kkk[0]-pre
			pr = kkk[0]
		if no[kkk[1]] == 0:
			no[kkk[1]] += 1
			co += 1
		else:
			no[kkk[1]] -= 1
			co -= 1
		pre = kkk[0]





else:
	for i in range(n):
		a,b = m()
		hq.heappush(po,[a,i])
		hq.heappush(po,[b,i])
	while len(po) != 0:
		kkk = hq.heappop(po)
		if co == (n // 2):
			if pre != pr:
				ans += 1
			ans += kkk[0]-pre
			pr = kkk[0]
		if no[kkk[1]] == 0:
			no[kkk[1]] += 1
			co += 1
		else:
			no[kkk[1]] -= 1
			co -= 1
		pre = kkk[0]


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis1=[];lis2=[]
for i in range(n):
    a,b=MI()
    lis1.append(a)
    lis2.append(b)
lis1.sort()
lis2.sort()
if n%2==1:
    ans=max(0,lis2[(n-1)//2]-lis1[(n-1)//2]+1)
else:
    sup1=lis2[n//2-1]
    sup2=lis2[n//2]
    low1=lis1[n//2-1]
    low2=lis1[n//2]
    ans=2*(sup2-low1)-1
    if sup1==sup2:
        ans+=1
    if low1==low2:
        ans+=1
    ans=max(ans,0)
print(ans)

Submission status: Wrong Answer

Solution code:
import statistics

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

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

    print(rightId - leftId + 1 - aaa)

Submission status: Wrong Answer

Solution code:
n = int(input())

A = []
B = []

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

m = int(((n * 2) - 2) / 2)

A.sort()
p = A[m - 1]
B.sort(reverse=True)
q = B[m-1]

if n % 2 == 1:
    print(q - p + 1)
else:
    print((q - p) * 2 - 1)

Submission status: Wrong Answer

Solution code:
import statistics
n=int(input())
r=set([])
x=[[]]*n
for i in range(n):
  a,b=list(map(int,input().split()))
  x[i]=[a,b]
r0=statistics.median([x[z][0] for z in range(n)])
r1=statistics.median([x[z][1] for z in range(n)])
if ((r0*2) % 2)>0 or ((r1*2) % 2)>0:
  mult=2
else:
  mult=1
mult=int((r1-r0)+mult)
print(mult)

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-1)]

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

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
ABs_desc = deepcopy(ABs)

ABs.sort(key=lambda x:(x[0],-x[1]))
ABs_desc.sort(key=lambda x: (-x[1],x[0]))

if N%2:
    for AB in ABs:
        if AB[0] == ABs[N//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[N//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    print(B2-A1+1)
else:
    for AB in ABs:
        if AB[0] == ABs[N//2][0]:
            A1,B1 = AB[0],AB[1]
            break
    for AB in ABs_desc:
        if AB[1] == ABs_desc[N//2][1]:
            A2,B2 = AB[0],AB[1]
            break
    print(B1+B2-A1-A2+1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

m=10**10
M=-1
r=0
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
    if a<=m:
        if b>r:
            r=b
            idm=i
        m=a
l=10**10
idM=-1
for i in range(N):
    a=A[i]
    b=B[i]
    if M<=b:
        if a<l:
            l=a
            idM=i
        M=b
G=[]
for i in range(N):
    a=A[i]
    b=B[i]
    G.append([a,b,i])

G.sort()
tmp=0
cnt=0
for i in range(N):
    num=G[i][2]
    if num==idm or num==idM:
        continue
    a=G[i][0]
    b=G[i][1]
    tmp=max(a,tmp)
    if tmp>=b:
        continue
    cnt+=b-tmp
    #print(a,b,tmp)
    tmp=b
cnt+=1

if N==2:
    #print("ON")
    tmp=0
    cnt=0
    for i in range(N):
        a=A[i]
        b=B[i]
        tmp=max(a,tmp)
        if tmp>=b:
            continue
        cnt+=b-tmp
        tmp=b
    cnt+=1
    ans=(cnt*(cnt-1))//2
    print(cnt)
    exit()


if N%2==1:
    print(cnt)
else:
    ans=(cnt*(cnt-1))//2
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a,b = [], []
for _ in range(n):
  i = input().split()
  a.append(int(i[0]))
  b.append(int(i[1]))
a.sort()
b.sort()
if n%2:
  l = a[n//2]
  h = b[n//2]
  print(l-h+1)
else :
  l = (a[n//2-1]+a[n//2]) / 2
  h = (b[n//2-1]+b[n//2]) / 2
  print(int((l-h)*2) +1)