「DPOI-1」道路规划

Luogu
IDLGP8896
Time1000ms
Memory128MB
DifficultyP4
贪心2022洛谷原创O2优化优先队列构造
战场上有 $n$ 个据点,从 $1\sim n$ 编号。**每两个据点**之间**都**有一条双向道路。 一天,总司令来战区巡视,走着走着迷路了,于是愤怒地下达命令,让你把每一条双向道路变成单向的,使得这些道路**不包含环**(否则总司令会迷路)。但由于每个据点的规模互不相同,总司令从第 $i$ 个据点出发沿着单向道路能**直接到达**的据点数量需要在 $[l_i,r_i]$ 之间。换言之,第 $i$ 个点的出度需要在 $[l_i,r_i]$ 之间。你需要告诉总司令有没有可能满足他的需求。 ## Input **本题有多组测试数据。** 第一行,一个整数 $T$,表示数据组数。 对于每组数据: 第一行,一个整数 $n$,表示据点数量; 第二行,$n$ 个整数 $l_1, l_2, \dots, l_n$; 第三行,$n$ 个整数 $r_1, r_2, \dots, r_n$。 ## Output 对于每组数据: 一行,一个字符串。若可以满足总司令的需求,一行 `YES`;否则,一行 `NO`。 [samples] ## Background 不可以,总司令。 ## Note #### 样例 #1 解释 下面是第 $1$ 组数据中一种可行的方案: ![](https://cdn.luogu.com.cn/upload/image_hosting/2uvwlydw.png) #### 样例 #2 解释 该样例满足测试点 $3 \sim 6$ 的限制。 #### 数据范围 **本题测试点分数不等分。** | 测试点编号 | $n \le$ | 特殊条件 |每个测试点分数| | :----------: | :-----------: | :------: | :----: | | $1\sim 2$ | $10$ | 无 |$5$| | $3\sim 6$ | $1000$ | 无 |$5$| | $7\sim 8$ | $10^5$ | 所有 $l_i = i-1$ 或所有 $l_i \geq \min (i, n - 1)$ |$5$| | $9 \sim 10$ | $10^5$ | $l_i=0$ 或 $r_i=n-1$ |$5$| | $11 \sim 15$ | $10^5$ | 无 |$10$| 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$0 \leq l_i \leq r_i < n$,$1 \leq T \leq 10$。
Samples
Input #1
2
5
0 1 4 0 0
3 4 4 1 3
3
1 2 2
2 2 2
Output #1
YES
NO
Input #2
见下发文件 road2.in
Output #2
见下发文件 road2.out
API Response (JSON)
{
  "problem": {
    "name": "「DPOI-1」道路规划",
    "description": {
      "content": "战场上有 $n$ 个据点,从 $1\\sim n$ 编号。**每两个据点**之间**都**有一条双向道路。 一天,总司令来战区巡视,走着走着迷路了,于是愤怒地下达命令,让你把每一条双向道路变成单向的,使得这些道路**不包含环**(否则总司令会迷路)。但由于每个据点的规模互不相同,总司令从第 $i$ 个据点出发沿着单向道路能**直接到达**的据点数量需要在 $[l_i,r_i]$ 之间。换言之,第 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8896"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "战场上有 $n$ 个据点,从 $1\\sim n$ 编号。**每两个据点**之间**都**有一条双向道路。\n\n一天,总司令来战区巡视,走着走着迷路了,于是愤怒地下达命令,让你把每一条双向道路变成单向的,使得这些道路**不包含环**(否则总司令会迷路)。但由于每个据点的规模互不相同,总司令从第 $i$ 个据点出发沿着单向道路能**直接到达**的据点数量需要在 $[l_i,r_i]$ 之间。换言之,第 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments