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), y(n);
    for(int i = 0; i < n; i++)
        cin >> x[i].first >> x[i].second;
    sort(x.begin(), x.end());
    y = x;
    reverse(y.begin(), y.end());

    if(n % 2 == 1)
    {
        int l = x[n / 2].first;
        int r = y[n / 2].second;
        cout << r - l + 1 << '\n';
    }
    else
    {
        int l1 = x[n / 2].first;
        int r1 = y[n / 2].second;
        int l2 = x[n / 2 - 1].first;
        int r2 = y[n / 2 - 1].second;
        
        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())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(kagen)
zz = sorted(zyogen)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[a]
    y = zz[aa-1] + zz[a]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)

Submission status: Runtime Error

Solution code:
n=int(input())
c=[list(map(int,input().split())) for _ in range(n)]
c.sort()
q,w=c[n//2][0],min(c[n//2][1],c[n//2+1][1])
c.sort(key=lambda x: x[1])
e,r=max(c[n//2][0],c[n//2-1][1]),c[n//2][1]
if w<=e:
    print(max(w-q,r-e)+1)
else:
    print(r-q+1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(k)
zz = sorted(z)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[a]
    y = zz[aa-1] + zz[a]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(k)
zz = sorted(z)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1] + kk[a]
    y = zz[aa-1] ++ + zz[a]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)

Submission status: Runtime Error

Solution code:
from itertools import product
n, *AB = map(int, open(0).read().split())
A, B = map(sorted, [AB[::2], AB[1::2]])
mid = n//2
if n % 2 == 0:
    a, b = A[mid-1], B[mid-1]
    X = range(a, b+1)
    a, b = A[mid], B[mid]
    Y = range(a, b+1)
    Z = {a+b for a, b in product(X, Y)}
    print(len(Z))
else:
    print(B[mid] - A[mid] + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
	A=[]
    B=[]
    for i in range(n):
        a,b=INTM()
        A.append(a)
        B.append(b)
        B=sorted(B,reverse=True)
    if n%2==1:
        ta=A[n//2]
        tb=B[n//2]
        print(tb-ta+1)
    else:
        ta1=A[n//2]
        ta2=A[n//2+1]
        tb1=B[n//2]
        tb2=B[n//2+1]
        avea=(ta1+ta2)/2
        aveb=(tb1+tb2)/2
        print(int((aveb-avea)*2)+1)
        
        
    
if __name__ == '__main__':
    do()

Submission status: Runtime Error

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 = math.ceil(y) - math.floor(x)
    print(2 * temp + 1))

Submission status: Runtime Error

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
	A=[]
    B=[]
    for i in range(n):
        a,b=INTM()
        A.append(a)
        B.append(b)
        B=sorted(B,reverse=True9
    if n%2==1:
        ta=A[n//2]
        tb=B[n//2]
        print(tb-ta+1)
    else:
        ta1=A[n//2]
        ta2=A[n//2+1]
        tb1=B[n//2]
        tb2=B[n//2+1]
        avea=(ta1+ta2)/2
        aveb=(tb1+tb2)/2
        print(int((aveb-avea)*2)+1)
        
        
    
if __name__ == '__main__':
    do()

Submission status: Runtime Error

Solution code:
n = int(input())
N = 10**9
x = [0]*(N+1)
x1= [0]*N
x2= [0]*N
for i in range(n):
    a , b = map(int, input().split())
    x[a-1]+=1
    x[b]-=1

for i in range(1,N):
    x[i]=x[i]+x[i-1]

for i in range(1,N):
    x1[i]=x1[i]+x1[i-1]

x.reverse()
for i in range(1,N):
    x2[i]=x2[i]+x2[i-1]

ans =0
if n % 2 == 1:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans)
else:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans*2+1)

Submission status: Runtime Error

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:
  m = sorted(A)[int(N/2)]
  M = sorted(B)[int(N/2)]
else:
  m = sorted(A)[int(N/2)]
  M = sorted(B)[int(N/2) + 1]
  
print(M - m + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
for _ in range(n):
    i = tuple(map(int,input().split()))
    l.append(i)
if n % 2 == 1:
    down = sorted(l)[(n+1)/2 - 1][0]
    up = sorted(l, key=lambda x:x[1])[(n+1)/2 -1][1]
    print(int(up - down))
else:
    down1 = sorted(l)[n/2 - 1][0]
    down2 = sorted(l)[n/2][0]
    up1 = sorted(l, key=lambda x:x[1])[n/2 - 1][1]
    up2 = sorted(l, key=lambda x:x[1])[n/2][1]
    print(((up1+up2)/2 - (down1+down2)/2)*2)

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:
n = int(input())
x,y = map(int,input().split())
a = [x]
b = [y]
for i in range(n-1):
    x,y = map(int,input().split())
    if(a[-1] < x):
        a.append(x)
    elif(a[0] > x):
        a = [x] + a
    else:
        for j in range(len(a)):
            if(a[j] < x):
                a.insert(j,x)
                break
    if(b[-1] < y):
        b.append(y)
    elif(b[0] > y):
        a = [y] + b
    else:
        for j in range(len(b)):
            if(b[j] < y):
                b.insert(j,y)
                break
if(n%2 == 1):
    print(abs(a[n//2]-b[n//2])+1)
else:
    print(abs(a[n//2] + a[-1+n//2] - b[n//2] - b[-1+n//2])+1)

Submission status: Runtime Error

Solution code:
n = int(input())

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

ls.sort()

ans = 0

left = ls[n/2][0]
ls.sort(key=lambda a: a[1])
right = ls[n/2][1]
ans = right - left + 1
if ans < 0:
    ans = 0
if n%2 == 0:
  ans = ans * 2

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
a.sort()
b.sort()
minm = (a[(n + 1) // 2 - 1] if n & 1 (a[(n + 1) // 2] + a[(n + 1) // 2 - 1]) * 0.5)
maxm = (b[(n + 1) // 2 - 1] if n & 1 (b[(n + 1) // 2] + b[(n + 1) // 2 - 1]) * 0.5)
print(maxm - minm + 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import itertools

# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
input_list = [list(map(int, input().split())) for i in range(N)]

flat_list = list(itertools.chain.from_iterable(input_list))

flg_list = [i+1 for i in range(N)]
if N%2 == 0:
    flg = 1
else:
    flg = 0
#print(input_list)
i = float(min(flat_list))
#for i in range(1000000000):
ans = ans+1
while i < max(flat_list):
    #print()
    #print(i)
    #print(flg_list)
    if i==1:
        if flg:
            i = i+0.5
        else:
            i=i+1
        continue
    big = 0
    small = 0
    newtral = 0
    for j in range(N):
        if i < input_list[j][0]:
            big = big+1
        elif input_list[j][1]:
            small = small+1
        else:
            newtral = newtral+1
    if abs(big - small) <= newtral:
        ans = ans+1
    #if abs(big - small) <= newtral:
        #for j in reversed(range(len(flg_list))):
            #if input_list[flg_list[j]-1][0] <= i and i <= input_list[flg_list[j]-1][1]:
                #del flg_list[j]
    if flg:
        i = i+0.5
    else:
        i=i+1
#print()
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = []
zyogen = []
kagen = []
for i in range(n):
    k, z = map(int, input().split())
    kagen.append(k)
    zyogen.append(z)

kk = sorted(k)
zz = sorted(z)
if(n % 2 == 0):
    aa = n // 2
    x = kk[aa-1]
    y = zz[aa]
    print(y-x+1)
else:
    aa = n // 2
    x = kk[aa]
    y = zz[aa]
    print(y-x+1)

Submission status: Runtime Error

Solution code:
n = int(input())
N = 10**9
x = [0]*(N+1)
x1= [0]*N
x2= [0]*N
for i in range(n):
    a , b = map(int, input().split())
    x[a-1]+=1
    x[b]-=1

for i in range(1,N):
    x[i]=x[i]+x[i-1]

for i in range(1,N):
    x1[i]=x1[i]+x1[i-1]

x.reverse()
for i in range(1,N):
    s2[i]=x2[i]+x2[i-1]

ans =0
if n % 2 == 1:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans)
else:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans*2+1)

Submission status: Runtime Error

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = []
    b = []
    d = []
    for _ in range(n):
        ai, bi = ns()
        a.append(ai)
        b.append(bi)
        d.append((ai, bi))

    a.sort()
    b.sort()

    odd = n % 2 == 1
    even = n % 2 == 0
    min_choice = a[n // 2 - even]
    max_choice = b[n // 2]

    kouho = []
    for ai, bi in d:
        tmp = range(max(ai, min_choice), min(bi, max_choice))
        if len(tmp) > 0:
            kouho.append(tmp)

    dic_even = dict()
    dic_odd = dict()

    for k in kouho:
        for t in k:
            dic_even[t] = 0

    for i in range(len(kouho)):
        for t in kouho[i]:
            for j in range(i + 1, len(kouho)):
                for l in kouho[j]:
                    dic_odd[(t + l) / 2] = 0
    
    e = set(dic_even.keys())
    o = set(dic_odd.keys())
    
    ans = e+o
    print(len(ans))


if __name__ == '__main__':
    main()

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:
N = int(input())

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

y = []
for i,j in x:
    y.append([j, i])

x.sort()
y.sort(reverse = True)

mini = 10 ** 10
maxi = 0
if N % 2 == 1:
    idx = (N+1) // 2 - 1
    for i,j in x[idx:]:
        mini = min(mini,j)
    for i,j in y[idx:]:
        maxi = max(maxi, j)
    if maxi <= mini:
        ans = y[idx][0] - x[idx][0] + 1 
    else:
        ams = y[idx][0] - maxi +mini - x[idx][0] + 2 
        
else:
    idx = N // 2
    for i,j in x[idx:]:
        mini = min(mini,j)
    for i,j in y[idx:]:
        maxi = max(maxi, j)
    if maxi + y[idx-1][1] <= mini + x[idx-1][1]:
        ans = y[idx][0]+y[idx-1][0] - x[idx][0]-x[idx-1][0] + 1
    else:
        ans = y[idx][0]+y[idx-1][0] - maxi - y[idx-1][1] +mini + x[idx-1][1] - x[idx][0]-x[idx-1][0]

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
for _ in range(n):
    i = tuple(map(int,input().split()))
    l.append(i)
if n % 2 == 1:
    down = sorted(l)[(n+1)/2 - 1][0]
    up = sorted(l, key=lambda x:x[1])[(n+1)/2 -1][1]
    print(int(up - down))
else:
    down1 = sorted(l)[n/2 - 1][0]
    down2 = sorted(l)[n/2][0]
    up1 = sorted(l, key=lambda x:x[1])[n/2 - 1][1]
    up2 = sorted(l, key=lambda x:x[1])[n/2][1]
    print(((up+up)/2 - (down1+down2)/2)*2)

Submission status: Runtime Error

Solution code:
import copy
import numpy as np
N = int(input())
x = []

def median(x_list):
    x_list = sorted(x_list)
    if N%2!=0:
        return x_list[(N+1)//2]
    else:
        return (x_list[N//2-1] + x_list[N//2 +1-1])/2

def dfs(x_list):
    medians = []
    if len(x_list)==N:
        med = median(x_list)
        return [med]
    else:
        idx = len(x_list)
        xrang = x[idx]
        x_list.append(-1)
        for i in range(xrang[0], xrang[1]+1):
            x_list[-1] = i
            r = dfs(copy.copy(x_list))
            medians.extend(r)
    return medians

for _ in range(N):
    mi,ma = [int(a) for a in input().split()]
    x.append((mi, ma))

ans = dfs([])
ans = len(np.unique(ans))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

ls.sort()

ans = 0

left = ls[n/2][0]
ls.sort(key=lambda a: a[1])
right = ls[n/2][1]
ans = right - left + 1
if ans < 0:
    ans = 0

print(ans)

Submission status: Runtime Error

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

def dfs(i,group):
    center=[]
    if i==n:
        group.sort()
        if n%2==1:
            center+=[group[int((n-1)/2)]]
            return
        else:
            center+=[group[int(n/2)]+group[int((n/2-1)/2)]]
            return
    s=T[i][0]
    g=T[i][1]
    for j in range(s,g+1):
        #print(i,group)
        dfs(i+1,group+[j])
dfs(0,[])
print(len(set(center)))

Submission status: Runtime Error

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 = a_sort[int(n/2)-1]
  b_med = b_sort[int(n/2)]
  v = int(((b_med-a_med+1)*(b_med-a_med))/2)
  
  for x in x_list:
    if x[0] == a_med and x[1] == b_med:
      v = v - a_med[int(n/2)] + a_med[int(n/2)-1] - b_sort[int(n/2)] + b_sort[int(n/2)-1]
      
  print(v)

Submission status: Runtime Error

Solution code:
from itertools import product
n, *AB = map(int, open(0).read().split())
A, B = AB[::2], AB[1::2]
A, B = map(sorted, [A, B])
mid = n//2
if n % 2 == 0:
    a, b = A[mid-1], B[mid-1]
    X = range(a, b+1)
    a, b = A[mid], B[mid]
    Y = range(a, b+1)
    Z = {(a+b)/2 for a, b in product(X, Y)}
    print(len(Z))
else:
    print(B[mid] - A[mid] + 1)

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
for _ in range(n):
    a,b = map(int,input().split())
    l.append(a)
    l.append(b)
l2 = sorted(list(set(l)))
length = len(l2)
if length == 1:
  print(l2[0])
  exit()
print(l2[length//2 + 1] - l2[length//2 - 1] + 1)

Submission status: Runtime Error

Solution code:
import statistics
n=int(input())
lst=[]
m=[]
M=[]
for i in range(n):
  a,b=map(int,input().split())
  m.append(a)
  M.append(b)
  lst.append([a,b])

cnt=0
for i in range(n):
  med_min=statics.median(m[:i]+m[i+1:])
  med_max=statics.median(M[:i]+M[i+1:])
  if med_min<=m[i] and M[i]<=med_max:
    cnt+=M[i]-m[i]
  elif med_min<=m[i] and M[i]>med_max:
    cnt+=med_max-m[i]
  elif med_min>m[i] and M[i]<=med_max:
    cnt+=M[i]-med_min
print(cnt)