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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()


class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

## Tested by EduFor 88 D
## https://codeforces.com/contest/1359/problem/D

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

 
show_flg=False
show_flg=True
ans=0


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

for i in rep(n):
    a,b=LI()
    A+=[a]
    B+=[b]

A.sort()
B.sort()
if n%2==0:
    kl=n//2-1
    kr=n//2
else:
    kl=n//2
    kr=n//2
lm,lM=A[kl],A[kr]
rm,rM=B[kl],B[kr]

if n%2==0:
    ans=lM+rM-lm-rm+1
else:
    ans=rm-lm+1


print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    A, B = LI()
    ans = A*B
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a==0:
            print(0)
            return
    ans = 1
    for a in A:
        ans *= a
        if ans>10**18:
            print(-1)
            return
    print(ans)
    return

def examC():
    A, B = list(map(float,input().split()))
    ans = (int(A*B*100))//100
    print(ans)
    return

def examD():
    def factorization(n):
        arr = defaultdict(int)
        temp = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr
    C = [0,1,3,6,10,15,21,28,36,45]
    N = I()
    F = factorization(N)
    ans = 0
    #print(F)
    for f in F.values():
        for i in range(10):
            if C[i]>f:
                ans += i-1
                break
    print(ans)
    return

def examE():
    N = I()
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    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)*2 +1
    else:
        L = A[N//2]
        R = B[N//2]
        ans = (R-L)+1

    print(ans)
    return

def examF():
    N, S = LI()
    A = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
n = int(input())

abl = [map(int,input().split()) for _ in range(n)]

al = []
bl = []

for a,b in abl:
    al.append(a)
    bl.append(b)

if n % 2 == 0:
    min_a = (al[n//2-1] + al[n//2]) / 2
    max_a = (bl[n//2-1] + bl[n//2]) / 2
else:
    min_a = al[(n-1)//2]
    max_a = bl[(n-1)//2]

if n % 2 == 0:
    print(int((max_a - min_a) * 2 + 1))
else:
    print(max_a - min_a + 1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    g = LIR(n)
    if n&1:
        g.sort()
        l = g[n>>1][0]
        g.sort(key = lambda x:x[1])
        r = g[n>>1][1]
        print(r-l+1)
    else:
        g.sort()
        l = g[(n>>1)-1][0]
        g.sort(key = lambda x:x[1])
        r = g[n>>1][1]
        print((r-l)*2-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
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==1:
    print(B[(N-1)//2] - A[(N-1)//2]+1)
else:
    b1 = B[(N-2)//2]
    b2 = B[N//2]
    a1 = A[(N-2)//2]
    a2 = A[N//2]
    print(a2 + b2 - (a1 + b1) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

abl = [map(int,input().split()) for _ in range(n)]

al = []
bl = []

for a,b in abl:
    al.append(a)
    bl.append(b)

if n % 2 == 0:
    min_a = (al[n//2-1] + al[n//2]) / 2
    max_a = (bl[n//2-1] + bl[n//2]) / 2
else:
    min_a = al[(n-1)//2]
    max_a = bl[(n-1)//2]

if n % 2 == 0:
    print(int(max_a - min_a) * 2 + 1)
else:
    print(max_a - min_a + 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==1:
    n = N//2
    print(sorted(B, reverse=True)[n]-sorted(A)[n]+1)
    exit()
l, r = (N-2)//2, N//2
A.sort()
B.sort()
print(A[r]-A[l]+B[r]-B[l]+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)

m1 = A[N//2] + A[(N-1)//2]
m2 = B[N//2] + B[(N-1)//2]
print((m2 - m1) // (N % 2 + 1) + 1)

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:

def merge(s, t):
    u = []

    while s + t:
        
        if s == [] or t == []:
            return u + s + t

        if s[0] <= t[0]:
            u.append(s[0])
            s = s[1:]
        else: # s0 > t0
            u.append(t[0])
            t = t[1:]

    return u

def merge_sort(A):
    while len(A) > 1:
        B = []
        for i in range(len(A) // 2):
            B.append(merge(A[2 * i], A[2 * i + 1]))
        if len(A) % 2 == 1:
            B.append(A[len(A) - 1])
        A = B

    return(A[0])

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

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

C = merge_sort(A)
D = merge_sort(B)

if N % 2 == 0:
    ans = D[N//2 - 1] + D[N//2] - C[N//2 - 1] - C[N//2] + 1
else: # N % 2 == 1
    ans = D[N//2] - C[N//2] + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A.sort()
B.sort()
N_q, N_mod = divmod(N, 2)
if N_mod == 1:
    ans = B[N_q] - A[N_q] + 1
else:
    ans_list = []
    for x in range(A[N_q - 1], B[N_q - 1] + 1, 1):
        for y in range(A[N_q], B[N_q] + 1, 1):
            ans_list.append((x + y) / 2)
    c = collections.Counter(ans_list)
    values, counts = zip(*c.most_common())
    ans = len(values)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

        
n = int(input())

a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)

for i in range(n):
    a[i],b[i] = map(float, input().split())

#listをsortする
if n==2:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])
else:
    a0 = [a[0]]
    b0 = [b[0]]
    if a[1]>=a[0]:
        a0.append(a[1])
    else:
        a0.insert(0,a[1])
    if b[1]>=a[0]:
        b0.append(b[1])
    else:
        b0.insert(0,b[1])    
    for i in range(2,n):
        if a[i]>=a0[len(a0)-1]:
            a0.append(a[i])
        elif a[i]<=a0[0]:
            a0.insert(0,a[i])
        else:
            l = 0
            for j in range(len(a0)-1):
                if a0[j]<=a[i] and a[i]<=a0[j+1] and l==0:
                    a0.insert(j+1,a[i])
                    l = 1
        if b[i]>=b0[len(b0)-1]:
            b0.append(b[i])
        elif b[i]<=b0[0]:
            b0.insert(0,b[i])
        else:
            m = 0
            for j in range(len(b0)-1):
                if b0[j]<=b[i] and b[i]<=b0[j+1] and m==0:
                    b0.insert(j+1,b[i])
                    m = 1

                    
if n%2 == 1:
    a0cen = a0[(n-1)//2]
    b0cen = b0[(n-1)//2]
    nn = b0cen - a0cen + 1
else:
    a0cen1 = a0[(n-2)//2]+a0[n//2]
    b0cen1 = b0[(n-2)//2]+b0[n//2]
    nn = int(b0cen1 -a0cen1 +1)

print(nn)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [None] * N
B = [None] * N

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

medians = []

if N % 2 == 0:
    a_median = (A[N // 2 - 1] + A[N // 2]) // 2
    b_median = (B[N // 2 - 1] + B[N // 2]) // 2
    i = a_median
    while i <= b_median:
        medians.append(i)
        i += 0.5
else:
    a_median = A[(N + 1) // 2 - 1]
    b_median = B[(N + 1) // 2 - 1]
    for i in range(a_median, b_median + 1):
        medians.append(i)

print(len(medians))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
AA = sorted(A)
BB = sorted(B)

if N%2==1:
    low = AA[N//2  ]
    high = BB[N//2  ]
    print(high - low +1)

else:
    low = (AA[N//2-1] + AA[N//2]) / 2
    high = (BB[N//2-1] + BB[N//2]) / 2
    #print(low,high)
    count=0
    while True:
        low +=  0.5
        count+=1
        if low==high:
            break
    #low = math.floor(low)
    #high = math.ceil(high)
    print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from statistics import median


n = int(input())
X = []

for _ in range(n):
    a, b = map(int, input().split())
    X.append(range(a, b+1))

# print(list(product(*X)))
print(len({median(i) for i in product(*X)}))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A0, B0 = map(int, input().split())
a = []
import copy
for i in range(A0,B0+1):
  a.append([i])
for i in range(N-1):
  A, B = map(int, input().split())
  n = len(a)
  for j in range(n):
    b = copy.copy(a[j])
    a[j].append(A)
    for k in range(A+1,B+1):
      a.append(b+[k])
if N%2 == 0:
  m = N//2
  B = []
  nn = len(a)
  for i in range(nn):
    B.append((a[i][m-1]+a[i][m])/2)
else:
  m = N//2
  B = []
  nn = len(a)
  for i in range(nn):
    B.append(a[i][m])
B = list(set(B))
ans = len(B)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    # s = input()
    n = int(input())
    # a, b = map(int, input().split())
    a_list = []
    b_list = []
    for _ in range(n):
        a, b = map(int, input().split())
        a_list.append(a)
        b_list.append(b)

    a_list.sort()
    b_list.sort()

    if n % 2 == 1:
        print(b_list[(n - 1) // 2] - a_list[(n - 1) // 2] + 1)
    else:
        lower = [a_list[n // 2 - 1], b_list[n // 2 - 1]]
        upper = [a_list[n // 2], b_list[n // 2]]

        ans = set()
        for i in range(lower[0], lower[1] + 1):
            for j in range(max(upper[0], i), upper[1] + 1):
                ans.add((i + j) / 2)

        print(len(ans))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 2
2 3"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
100 100
10 10000
1 1000000000"""
        output = """9991"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    # s = input()
    n = int(input())
    # a, b = map(int, input().split())
    a_list = []
    b_list = []
    for _ in range(n):
        a, b = map(int, input().split())
        a_list.append(a)
        b_list.append(b)

    a_list.sort()
    b_list.sort()

    if n % 2 == 1:
        print(b_list[(n - 1) // 2] - a_list[(n - 1) // 2] + 1)
    else:
        lower = [a_list[n // 2 - 1], b_list[n // 2 - 1]]
        upper = [a_list[n // 2], b_list[n // 2]]

        ans = set()
        for i in range(lower[0], lower[1] + 1):
            for j in range(max(upper[0] , i), upper[1] + 1):
                ans.add((i + j) / 2)

        print(len(ans))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 2
2 3"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
100 100
10 10000
1 1000000000"""
        output = """9991"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

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


sA = sorted(A)
sB = sorted(B, reverse=True)



m = N//2

if N%2 == 1:
    minMid = sA[m]
    maxMid = sB[m]

    print(maxMid-minMid+1)
    exit()
else:
    m = m-1
    minMidL = sA[m]
    maxMidL = sB[m+1]

    minMidH = sA[m+1]
    maxMidH = sB[m]
    # print(minMidL, maxMidL)
    # print(minMidH, maxMidH)
    # print("=======")
    ans = set()
    for i in range(minMidL, maxMidL+1):
        for j in range(max(i, minMidH), maxMidH+1):
            # print(i, j)
            ans.add(i+j)
    print(len(ans))

Submission status: Time Limit Exceeded

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

A.sort()
B.sort()

if N % 2 == 1:
    index = int((N-1)/2)
    minX = A[index]
    maxX = B[index]
    ans = maxX - minX + 1
else:
    index = int(N/2)
    minX1 = A[index-1]
    minX2 = A[index]
    maxX1 = B[index-1]
    maxX2 = B[index]
    X = set()
    for i in range(minX1, maxX1+1):
        for j in range(minX2, maxX2+1):
            X.add((i+j)/2)
    ans = len(X)

print(ans)

Submission status: Time Limit Exceeded

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:
    retval=[]
    for x1 in range(A[N//2-1],B[N//2-1]+1):
        for x2 in range(A[N//2],B[N//2]+1):
            retval.append(x1+x2)
    print(len(set(retval)))

Submission status: Time Limit Exceeded

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]
    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: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  bisect.insort_left(al,ab[0])
  bisect.insort_left(bl,ab[1])
if n%2 == 1:
  z = (n+1)//2-1
  print(bl[z]-al[z]+1)
else:
  x = n//2
  ax2 = al[x-1]+al[x]
  bx2 = bl[x-1]+bl[x]
  print(bx2-ax2+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  al.append(ab[0])
  bl.append(ab[1])
  al.sort()
  bl.sort()
if n%2 == 1:
  z = (n+1)//2-1
  print(bl[z]-al[z]+1)
else:
  x = n//2
  ax2 = al[x-1]+al[x]
  bx2 = bl[x-1]+bl[x]
  print(bx2-ax2+1)

Submission status: Time Limit Exceeded

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)]
tAB = list(zip(*AB))
A = list(tAB[0]).copy()
B = list(tAB[1]).copy()
A.sort()
B.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import statistics

N = int(input())

A = []
B = []

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

count = 0

median = []

for i in range(A[0], B[0] + 1):
    for j in range(A[1], B[1] + 1):
        x = [i, j]
        cur_med = statistics.median(x)
        if cur_med not in median:
            median.append(cur_med)

print(len(median))

Submission status: Accepted

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

array1.sort()
array2.sort()

if N % 2 == 0:
    min = array1[N//2]+array1[N//2-1]
    max = array2[N//2]+array2[N//2-1]
    print(max-min+1)
else:
    min = array1[N//2]
    max = array2[N//2]
    print(max-min+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()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

#############
# Main Code #
#############

N = getN()
A = []
B = []
for i in range(N):
    a, b = getNM()
    A.append(a)
    B.append(b)
A.sort()
B.sort()
# 範囲がN個ある
# Xは整数
# 中央値のmin, maxは？
# Nが偶数、奇数の場合
# 奇数の場合 中央値は絶対に整数
# 中央値のmin: Aの中央値、max: Bの中央値
# 偶数の場合
# 中央値のmin: (Ai-1 + Ai) / 2 max: (Bi-1 + Bi) / 2
# いくつある？

# 中央値は最低でも0.5刻み
# 偶数の場合は奇数の2N - 1になる？
# Ai-1とAiを自由にいじることで0.5, 1, 1.5と言う風に中間値を作れそう
if N % 2 == 0:
    opt_a = (A[(N // 2) - 1] + A[N // 2]) / 2
    opt_b = (B[(N // 2) - 1] + B[N // 2]) / 2
    # opt_b - opt_aを0.5で割って +1
    print(int((opt_b - opt_a) * 2 + 1))
else:
    opt_a = A[N // 2]
    opt_b = B[N // 2]
    # 中央値は絶対に整数
    print(opt_b - opt_a + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

n = int(input())
A = [[int(i) for i in input().split()]for j in range(n)]    # nは行数

tmp = 0
res = 0

x = np.median(np.array(A), axis=0)
if n % 2 == 0:
    res = int((x[1] - x[0]) * 2 + 1)
else:
    res = int(x[1] - x[0] + 1)

print(res)