Packing Under Range Regulations

AtCoder

IDabc214_e

Time3000ms

Memory256MB

Difficulty—

Solve the following problem for $T$ test cases. There are $10^9$ boxes numbered $1,2,\dots,10^9$ and $N$ balls numbered $1,2,\dots,N$. Each box can contain at most one ball. Determine whether it is possible to put all $N$ balls in the boxes so that the following condition will be satisfied. * For each integer $i$ from $1$ through $N$, the ball numbered $i$ is in a box numbered between $L_i$ and $R_i$ (inclusive). ## Constraints * $1 \le T \le 2 \times 10^5$ * $1 \le N \le 2 \times 10^5$ * $1 \le L_i \le R_i \le 10^9$ * The sum of $N$ across the test cases in one input is at most $2 \times 10^5$. ## Input Input is given from Standard Input. The first line is in the following format: $T$ Then, $T$ test cases follows, each of which is in the following format: $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\dots$ $L_N$ $R_N$ [samples]

Samples

Input #1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Output #1

Yes
No

This input contains two test cases.

*   In the $1$\-st test case, the following way to put the three balls would satisfy the condition, so we should print `Yes`.
    *   Put Ball $1$ in Box $1$.
    *   Put Ball $2$ in Box $2$.
    *   Put Ball $3$ in Box $3$.
*   In the $2$\-nd test case, there is no way to put the five balls to satisfy the condition, so we should print `No`.

API Response (JSON)

{
  "problem": {
    "name": "Packing Under Range Regulations",
    "description": {
      "content": "Solve the following problem for $T$ test cases. There are $10^9$ boxes numbered $1,2,\\dots,10^9$ and $N$ balls numbered $1,2,\\dots,N$.   Each box can contain at most one ball.   Determine whether it i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc214_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Solve the following problem for $T$ test cases.\nThere are $10^9$ boxes numbered $1,2,\\dots,10^9$ and $N$ balls numbered $1,2,\\dots,N$.  \nEach box can contain at most one ball.  \nDetermine whether it i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments