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:
#include <iostream>
#include <iomanip>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <bitset>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
 
using namespace std;
 
#define R 1000000007
#define M 998244353
#define grid vector<vector<long long>>
#define L 256
#define INF 1000000000000000000LL

long long mx = INT32_MIN, mn = INT32_MAX;

struct maths_util
{
    vector<long long> fact;
    vector<bool> is_prime;
    maths_util(int n = 200001, long long q = R)
    {
        fact.resize(n);
        is_prime.assign(n + 1, true);

        fact[0] = 1;
        for(int i = 1; i < n; i++)
            fact[i] = (fact[i-1] * i) % q;

        is_prime[0] = is_prime[1] = false;
        for(int i = 2; i <= n; i++)
            if(is_prime[i])
                for(int j = i + i; j <= n; j += i)
                    is_prime[j] = false;
    }
    long long power_mod_q(long long x, long long n, long long q = R)
    {
        if(n == 0)
            return 1;
        if(n % 2 == 0)
            return power_mod_q((x * x) % q, n / 2, q);
        else 
            return (x * power_mod_q((x * x) % q, n / 2, q)) % q; 
    }

    long long inverse_mod_q(long long n, long long q = R)
    {
        return power_mod_q(n, q-2, q);
    }

    long long nCr_mod_q(long long n, long long r, long long q = R)
    {
        return (((fact[n] * inverse_mod_q(fact[r], q)) % q) * inverse_mod_q(fact[n-r], q)) % q;
    }

    long long power(long long x, long long n)
    {
        if(n == 0)
            return 1;
        if(n % 2 == 0)
            return power(x * x, n / 2);
        else 
            return x * power(x * x, n / 2); 
    }

    grid multiply(grid& a, grid& b)
    {
        int p = a.size(), q = b.size(), r = b[0].size();
        grid c(p, vector<long long>(r, 0));
        for(int i = 0; i < p; i++)
            for(int j = 0; j < r; j++)
                for(int k = 0; k < q; k++)
                    c[i][j] += a[i][k] * b[k][j];
        return c;
    }

    grid add(grid& a, grid& b)
    {
        int p = a.size(), q = a[0].size();
        grid c(p, vector<long long>(q));
        for(int i = 0; i < p; i++)
            for(int j = 0; j < q; j++)
                c[i][j] = a[i][j] + b[i][j];
        return c;
    }

    grid power(grid& a, long long n)
    {
        grid c(a.size(), vector<long long>(a.size(), 0));
        if(n == 0)
        {
            for(int i = 0; i < a.size(); i++)
                c[i][i] = 1;
            return c;
        }
        if(n % 2 == 0)
            return power(c = multiply(a, a), n / 2);
        else
            return multiply(a, c = power(c = multiply(a, a), n / 2));
        
    }
}u(1000001);

struct dsu
{
    vector<int> rank, parent, num;
    dsu(int n)
    {
        rank.assign(n, 0);
        parent.resize(n);
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find_set(int i)
    {
        if(i == parent[i])
            return i;
        return parent[i] = find_set(parent[i]);
    }
    bool is_same_set(int i, int j)
    {
        if(find_set(i) == find_set(j))
            return true;
        return false;
    }
    void union_set(int i, int j)
    {
        if(!is_same_set(i, j))
        {
            int u = find_set(i), v = find_set(j);
            if(rank[u] == rank[v])
            {
                parent[v] = u;
                rank[u] += 1;
            }
            else if(rank[u] > rank[v])
                parent[v] = u;
            else 
                parent[u] = v;
        }
    }

};

struct graph
{
    int v, time, count;
    vector<pair<int, int>>* adj;
    grid matrix;
    vector<bool> visited, in_stack, ap, in_MST;
    stack<int> s;
    vector<int> color, cc, f, d, finish_time, l, indegree, sccs, topo, outdegree, pred, child;
    vector<long long> dist;
    graph(int n)
    {
        v = n;
        adj = new vector<pair<int, int>>[n];
        // matrix.resize(n);
        // for(int i = 0; i < n; i++)
        //     matrix[i].assign(n, 0);
    }

    void add_edge(int u, int v, int w)
    {
        adj[u].push_back(make_pair(v, w));
        // adj[v].push_back(make_pair(u, w));
        // matrix[u][v] = w;
        // matrix[v][u] = w;
    }

    void dfs()
    {
        color.assign(v, 0);
        cc.assign(v, -1);
        d.assign(v, -1);
        f.assign(v, -1);
        time = count = 0;
        finish_time.assign(2 * v, -1);
        visited.assign(v, false);
        pred.assign(v, -1);
        for(int i = 0; i < v; i++)
        {
            if(color[i] == 0)
            {
                dfs(i);
                count++;
            }
        }
        for(int i = 0; i < v; i++)
            finish_time[f[i]] = i;
    }

    void dfs(int i)
    {
        color[i] = 1;
        cc[i] = count;
        d[i] = time;
        time++;
        for(auto x : adj[i])
        {
            if(!color[x.first])
            {
                pred[x.first] = i;
                dfs(x.first);
            }
        }
        color[i] = 2;
        f[i] = time;
        time++;
    }

    void bfs(int u)
    {
        color.assign(v, 0);
        pred.assign(v, -1);
        d.assign(v, 0);
        queue<int> q;
        color[u] = 1;
        q.push(u);
        while(!q.empty())
        {
            int i = q.front();
            q.pop();
            for(auto x : adj[i])
            {
                if(!color[x.first])
                {
                    pred[x.first] = i;
                    color[x.first] = 1;
                    d[x.first] = d[i] + 1;
                    q.push(x.first);
                }
            }
            color[i] = 2;
        }
    }

    void scc()
    {
        graph g_t(v);
        for(int i = 0; i < v; i++)
            for(auto x : adj[i])
                g_t.add_edge(x.first, i, x.second);
        dfs();
        for(int i = 2 * v - 1; i >= 0; i--)
        {
            if(finish_time[i] != -1 && g_t.color[finish_time[i]] == 0)
            {
                g_t.dfs(finish_time[i]);
                g_t.count++;
            }
        }
        sccs = g_t.cc;
        count = g_t.count;
    }

    void topological_sort()
    {
        indegree.assign(v, 0);
        outdegree.assign(v, 0);
        for(int i = 0; i < v; i++)
            if(adj[i].size())
                outdegree[i] = adj[i].size();
        for(int i = 0; i < v; i++)
            for(auto x : adj[i])
                indegree[x.first]++;
        vector<int> zero;
        for(int i = 0; i < v; i++)
            if(!indegree[i])
                zero.push_back(i);
        
        while(!zero.empty())
        {
            int v = zero.back();
            topo.push_back(v);
            zero.pop_back();
            for(auto x : adj[v])
            {
                indegree[x.first]--;
                if(!indegree[x.first])
                    zero.push_back(x.first);
            }
        }
    }

    void tarjan()
    {
        for(int i = 0; i < v; i++)
            if(!color[i])
                tarjan(i);
    }
    void tarjan(int i)
    {
        color[i] = 1;
        d[i] = time;
        time++;
        l[i] = d[i];
        s.push(i);
        in_stack[i] = true;
        for(auto x : adj[i])
        {
            if(!color[x.first])
            {
                tarjan(x.first);
                l[i] = min(l[i], l[x.first]);
            }
            else if(in_stack[x.first])
            {
                l[i] = min(l[i], d[x.first]);
            }
        }
        
        color[i] = 2;
        f[i] = time;
        time++;
        if(d[i] == l[i])
        {
            while(s.top() != i)
                cout << s.top() << ' ', in_stack[s.top()] = false, s.pop();
            cout << s.top() << '\n', in_stack[s.top()] = false, s.pop();
        }
    }

    graph kruskal()
    {
        vector<pair<int, pair<int, int>>> edges;
        for(int i = 0; i < v; i++)
            for(auto x : adj[i])
                edges.push_back(make_pair(x.second, make_pair(i, x.first)));
        sort(edges.begin(), edges.end());
        dsu d(v);
        graph mst(v);
        for(auto x : edges)
        {
            if(!d.is_same_set(x.second.first, x.second.second))
            {
                mst.add_edge(x.second.first, x.second.second, x.first);
                d.union_set(x.second.first, x.second.second);
            }

        }
        return mst;
    }

    graph prims(int s)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
        d.assign(v, INT32_MAX);
        pred.assign(v, -1);
        in_MST.assign(v, false);
        count = 0;
        d[s] = 0;
        pq.push({0, s});
        while(count < v)
        {
            int u = pq.top().second;
            if(!in_MST[u])
                in_MST[u] = true, count++;
            pq.pop();
            for(auto x : adj[u])
            {
                if(!in_MST[x.first] && d[x.first] > x.second)
                {
                    pq.push({x.second, x.first});
                    pred[x.first] = u;
                    d[x.first] = x.second;
                }
            }
        }
        graph mst(v);
        for(int i = 0; i < v; i++)
        {
            if(pred[i] != -1)
                mst.add_edge(i, pred[i], d[i]);
        }
        return mst;
    }

    void dijkstra(int s)
    {
        d.assign(v, INT32_MAX);
        visited.assign(v, false);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({d[s] = 0, s});
        while(!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if(!visited[u])
            {
                visited[u] = true;
                for(auto x : adj[u])
                {
                    if(d[x.first] > d[u] + x.second)
                    {
                        d[x.first] = d[u] + x.second;
                        pq.push({d[x.first], x.first});
                    }
                }
            }
        }
    }

};

struct kmp
{
    vector<int> lps;
    string p, t;
    kmp(string& p, string& t)
    {
        this -> p = p;
        this -> t = t;
        //PREPROCESSING
        lps.assign(p.size(), 0);
        lps[0] = 0;
        int len = 0, i = 1, j;
        while(i < p.size())
        {
            if(p[i] == p[len])
                lps[i++] = ++len;
            else if(len)
                len = lps[len-1];
            else 
                lps[i++] = 0;
        }
        //STRING MATCHING
        i = j = 0;
        while(i < t.size())
        {
            if(p[j] == t[i])
                j++, i++;
            
            if(j == p.size())
            {
                //It's a match at index i - 1
                j = lps[j-1];
            }
            else if(i < t.size() && p[j] != t[i])
            {
                if(j)
                    j = lps[j-1];
                else 
                    i++;
            }
        }

        
    }
};

struct trie
{
    struct node
    {
        char c;
        bool is_leaf;
        vector<node *> child;
        node(char ch)
        {
            c = ch;
            is_leaf = false;
            child.assign(L, nullptr);
        }
    };
    node * root;
    trie()
    {
        root = new node('#');
    }

    void insert(string& s)
    {
        node * temp = root;
        for(auto x : s)
        {
            if(!(temp -> child)[x])
                (temp -> child)[x] = new node(x);
            temp = (temp -> child)[x];
        }
        temp -> is_leaf = true;
    }

    bool has_child(node * temp)
    {
        for(auto x : temp -> child)
            if(x)
                return true;
        return false;
    }

    bool search(string& s)
    {
        node * temp = root;
        bool flag = true;
        for(auto x : s)
        {
            if(!(temp -> child)[x])
            {
                flag = false;
                break;
            }
            temp = (temp -> child)[x];
        }
        if(flag && temp -> is_leaf)
            return true;
        else
            return false;
    }

    void remove(string& s)
    {
        if(search(s))
            root = remove(root, 0, s);
    }
    node * remove(node * root, int pos, string& s)
    {
        if(pos <= s.length() - 1)
        {
            (root -> child)[s[pos]] = remove((root -> child)[s[pos]], pos + 1, s);
            bool flag = true;
            for(int i = 0; i < L; i++)
                if((root -> child)[i])
                    flag = false;
            if(root -> c != '#' && root -> is_leaf == false && flag)
            {
                delete(root);
                root = nullptr;
            }
        }
        else
        {
            root -> is_leaf = false;

            bool flag = true;
            for(int i = 0; i < L; i++)
                if((root -> child)[i])
                    flag = false;
            if(flag)
            {
                delete(root);
                root = nullptr;
            }
        }
        return root;
    }
};

bool isOverflow(long long a, long long b) 
{ 
    // Check if either of them is zero 
    if (a == 0 || b == 0)  
        return false; 
      
    long long result = a * b; 
    if (a == result / b) 
        return false; 
    else
        return true; 
} 


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<int, int>> x(n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
    {
        cin >> x[i].first >> x[i].second;
        a[i] = x[i].first;
        b[i] = x[i].second;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    if(n % 2 == 1)
    {
        int l = a[n / 2];
        int r = b[n / 2];
        cout << r - l + 1 << '\n';
    }
    else
    {
        int l1 = a[n / 2];
        int r1 = b[n / 2];
        int l2 = a[n / 2 - 1];
        int r2 = b[n / 2 - 1];
        
        int l = (l1 + l2), r = (r1 + r2);
        cout << r - l + 1 << '\n';
    }
    

    // int n;
    // cin >> n;
    // bool flag = false;
    // vector<long long> a(n);
    // for(int i = 0; i < n; i++)
    // {
    //     cin >> a[i];
    //     if(a[i] == 0)
    //         flag = true;
    // }
    // long long p = 1;
    // if(flag)
    // {
    //     cout << "0\n";
    //     return 0;
    // }
    // for(int i = 0; i < n; i++)
    // {
    //     if(isOverflow(p, a[i]))
    //     {
    //         cout << "-1\n";
    //         return 0;
    //     }
    //     p *= a[i];  
    // }
    // // cout << 1000000000000000000LL << '\n';
    // if(p > 1000000000000000000LL)
    //     cout << "-1\n";
    // else
    //     cout << p << '\n';
    
    return 0;
}

Submission status: Runtime Error

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()
#print(A)
#print(B)
if N % 2 == 1:
    AA = A[(N+1)//2]
    BB = B[(N+1)//2-1] 
    print(BB-AA+1)
else:
    AA = (A[N//2]+A[N//2+1])//2
    BB = (B[N//2-1]+B[N//2+1-1])//2
    print(BB-AA+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = np.zeros(N)
B = np.zeros(N)
for i in range(N):
    A[i], B[i] = map(int, input().split())

am = np.median(A)
bm = np.median(B)

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

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = []
B = []
for _ in range(N):
    A[i], B[i] = map(int, input().split())

A = np.array(A)
B = np.array(B)
am = np.median(A)
bm = np.median(B)

if n % 2 == 0:
    print((bm - am) * 2 + 1)
else:
    print((bm - am) + 1)

Submission status: Runtime Error

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

if n / 2 == 0:
    Am = (A[N / 2] + A[(N / 2) + 1]) / 2
    Bm = (B[N / 2] + B[(N / 2) + 1]) / 2
    print((Bm - Am) * 2 + 1)
else:
    Am = A[(N + 1) / 2]
    Bm = B[(N + 1) / 2]
    print(Bm - Am + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
A = []
B = []
for _ in range(n):
    A[i], B[i] = map(int, input().split())

if n / 2 == 0:
    Am = (A[N / 2] + A[(N / 2) + 1]) / 2
    Bm = (B[N / 2] + B[(N / 2) + 1]) / 2
    print((Bm - Am) * 2 + 1)
else:
    Am = A[(N + 1) / 2]
    Bm = B[(N + 1) / 2]
    print(Bm - Am + 1)

Submission status: Runtime Error

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()
a = (A[N-1//2] + A[N//2]+1)//2
b = (B[N-1//2] + B[N//2])//2
print(b-a+1)

Submission status: Runtime Error

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:
    print(re)

Submission status: Runtime Error

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()
a = (A[N-1//2] + A[N//2])//2
b = (B[N-1//2] + B[N//2])//2
print(b-a+1)

Submission status: Runtime Error

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()
a = (A[N+1//2] + A[N+2//2])//2
b = (B[N+1//2] + B[N+2//2])//2
print(b-a+1)

Submission status: Runtime Error

Solution code:
N = int(input())
L = list()
for _ in range(N):
    A, B = map(int, input().split())
    L.append((A, B))
L = sorted(L, key=lambda x: x[0])

if N%2 == 1:
    W = L[N//2]
    for l in range(N//2, -1, -1):
        if W[0] <= l[1]:
            W = (l[0], W[1])
        else:
            break
    for l in range(N//2, N):
        if l[0] <= W[1]:
            W = (W[0], l[1])
    print(W[1] - W[0] + 1)
else:
    W = L[N//2 - 1]
    V = L[N//2]
    ans = max(W[1] - W[0] + 1, V[1] - V[0] + 1)
    if W[1] >= V[0]:
        print(2*ans - 1)
    else:
        print(ans + 2)