#P8896. 「DPOI-1」道路规划

    ID: 8057 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>贪心2022洛谷原创O2优化优先队列构造

「DPOI-1」道路规划

题目背景

不可以,总司令。

题目描述

战场上有 nn 个据点,从 1n1\sim n 编号。每两个据点之间有一条双向道路。

一天,总司令来战区巡视,走着走着迷路了,于是愤怒地下达命令,让你把每一条双向道路变成单向的,使得这些道路不包含环(否则总司令会迷路)。但由于每个据点的规模互不相同,总司令从第 ii 个据点出发沿着单向道路能直接到达的据点数量需要在 [li,ri][l_i,r_i] 之间。换言之,第 ii 个点的出度需要在 [li,ri][l_i,r_i] 之间。你需要告诉总司令有没有可能满足他的需求。

输入格式

本题有多组测试数据。

第一行,一个整数 TT,表示数据组数。

对于每组数据:

第一行,一个整数 nn,表示据点数量;

第二行,nn 个整数 l1,l2,,lnl_1, l_2, \dots, l_n

第三行,nn 个整数 r1,r2,,rnr_1, r_2, \dots, r_n

输出格式

对于每组数据:

一行,一个字符串。若可以满足总司令的需求,一行 YES;否则,一行 NO

2
5
0 1 4 0 0
3 4 4 1 3
3
1 2 2
2 2 2
YES
NO
见下发文件 road2.in
见下发文件 road2.out

提示

样例 #1 解释

下面是第 11 组数据中一种可行的方案:

样例 #2 解释

该样例满足测试点 363 \sim 6 的限制。

数据范围

本题测试点分数不等分。

测试点编号 nn \le 特殊条件 每个测试点分数
121\sim 2 1010 55
363\sim 6 10001000
787\sim 8 10510^5 所有 li=i1l_i = i-1 或所有 limin(i,n1)l_i \geq \min (i, n - 1)
9109 \sim 10 li=0l_i=0ri=n1r_i=n-1
111511 \sim 15 1010

对于 100%100\% 的数据,1n1051 \leq n \leq 10^50liri<n0 \leq l_i \leq r_i < n1T101 \leq T \leq 10