Range Point Distance

AtCoder

IDarc129_b

Time2000ms

Memory256MB

Difficulty—

For integers $l$, $r$, and $x$ ($l \leq r$), let us define $dist(l,r,x)$ as follows. * If $x<l$: $dist(l,r,x)=l-x$ * If $l \leq x \leq r$: $dist(l,r,x)=0$ * If $r<x$: $dist(l,r,x)=x-r$ You are given $N$ pairs of integers, the $i$\-th of which is $(L_i,R_i)$. For each $k=1,2,\cdots,N$, solve the following problem. * Let us choose an integer $x$ freely and compute $\max(dist(L_1,R_1,x),dist(L_2,R_2,x),\cdots,dist(L_k,R_k,x))$. Find the minimum possible value of this. ## Constraints * $1 \leq N \leq 2 \times 10^5$ * $1 \leq L_i \leq R_i \leq 10^9$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ [samples]

Samples

Input #1

Output #1

0
0
1

*   For $k=1$, an optimal choice is $x=1$.
*   For $k=2$, an optimal choice is $x=3$.
*   For $k=3$, an optimal choice is $x=4$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Range Point Distance",
    "description": {
      "content": "For integers $l$, $r$, and $x$ ($l \\leq r$), let us define $dist(l,r,x)$ as follows. *   If $x<l$: $dist(l,r,x)=l-x$ *   If $l \\leq x \\leq r$: $dist(l,r,x)=0$ *   If $r<x$: $dist(l,r,x)=x-r$ You are",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc129_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For integers $l$, $r$, and $x$ ($l \\leq r$), let us define $dist(l,r,x)$ as follows.\n\n*   If $x<l$: $dist(l,r,x)=l-x$\n*   If $l \\leq x \\leq r$: $dist(l,r,x)=0$\n*   If $r<x$: $dist(l,r,x)=x-r$\n\nYou are...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments