{"problem":{"name":"Count Median","description":{"content":"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.","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc169_e"},"statements":[{"statement_type":"Markdown","content":"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.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq B_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_N$ $B_N$\n\n[samples]\n\n## Notes\n\nThe 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.\n\n*   If $N$ is odd, the median is $x_{(N+1)/2}$;\n*   if $N$ is even, the median is $(x_{N/2} + x_{N/2+1}) / 2$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc169_e","tags":[],"sample_group":[["2\n1 2\n2 3","3\n\n*   If $X_1 = 1$ and $X_2 = 2$, the median is $\\frac{3}{2}$;\n    \n*   if $X_1 = 1$ and $X_2 = 3$, the median is $2$;\n    \n*   if $X_1 = 2$ and $X_2 = 2$, the median is $2$;\n    \n*   if $X_1 = 2$ and $X_2 = 3$, the median is $\\frac{5}{2}$.\n    \n\nThus, the median can take three values: $\\frac{3}{2}$, $2$, and $\\frac{5}{2}$."],["3\n100 100\n10 10000\n1 1000000000","9991"]],"created_at":"2026-03-03 11:01:14"}}