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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n)]
    if n % 2 != 0:
        a, b = ab[n // 2]
        print(b - a + 1)
    else:
        a1, b1 = ab[(n - 1) // 2]
        a2, b2 = ab[(n + 1) // 2]
        print(len(list(range(a1 + a2, b1 + b2 + 1))))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N = int(input())

AB = [tuple(map(int, input().split())) for _ in range(N)]
ALL = []
ALL_append = ALL.append
for a, b in AB:
    ALL_append(a)
    ALL_append(b)

ALL.sort()
dic = dict()
for i, x in enumerate(ALL):
    dic[x] = i

lst1 = [0] * (2 * N + 1)
lst2 = [0] * (2 * N + 1)

for a, b in AB:
    lst1[dic[a]] += 1
    lst2[dic[b]] -= 1

for i in range(2 * N):
    lst1[i + 1] += lst1[i]
    lst2[2 * N - 1 - i] += lst2[2 * N - i]

# print (lst1)
# print (lst2)

if N % 2 == 1: #奇数 -->一意に決まる時
    left = bisect_left(lst1, N // 2 + 0.5)
    right = bisect_left(lst2, -((N) // 2) - 0.5) - 1
    # print (left, right)
    upper = ALL[right]
    lower = ALL[left]
    print (upper - lower + 1)
else:
    left = bisect_left(lst1, N // 2 - 0.5)
    right = bisect_left(lst2, -(N // 2) - 0.5)
    # print (left, right)
    upper = ALL[right]
    lower = ALL[left]
    print (upper - lower + 1)

Submission status: Runtime Error

Solution code:
a,b=input().split()
print(int(a)*int(float(b)*100)//100)

Submission status: Runtime Error

Solution code:
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll n,min_v,max_v;
  cin >> n;
  vector<ll> a(n),b(n);
  vector<ll> mi(n),ma(n);
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i];
    if(n%2==0){
      a[i] *= 2;
      b[i] *= 2;
    }
    mi[i] = a[i];
    ma[i] = b[i];
  }
  sort(mi.begin(),mi.end());
  sort(ma.begin(),ma.end());
  if(n%2){
    min_v = mi[n/2];
    max_v = ma[n/2];
  }else{
    min_v = (mi[n/2]+mi[n/2-1])/2;
    max_v = (ma[n/2]+ma[n/2-1])/2;
  }
  cout << max_v - min_v + 1<<endl;
}

Submission status: Runtime Error

Solution code:
N = int(input())
A_Vals = list()
B_Vals = list()
for n in range(N):
  a, b = input().split()
  A_Vals.append(int(a))
  B_Vals.append(int(b))
res = 0
if N%2:
  num = N//2
  res = B_Vals[num]-A_Vals[num]+1
else:
  lst = list()
  id = N/2-1
  for X1 in range(A_vals[id], B_Vals[id]+1):
    for X2 in range(A_vals[id+1], B_Vals[id+1]+1):
      num = (X1+X2)/2
      if num not in lst:
        lst.append(num)
  res = len(lst)
print(res)