/ Vijos / 题库 /

线段匹配

线段匹配

时间限制:1秒  内存限制:256M


【题目描述】

  小沐同学手上有两类线段,分别为A线段和B线段。

  A线段的有 \(n\) 种,第i种有 \(s_i\) 条,其左端点和右端点为 \(a_i\) 和 \(b_i\),他们都是 \(10^9\) 范围内的正整数,且一定有 \(a_i≤b_i\)。B线段的有 \(m\) 种,第 \(i\) 种有 \(k_i\) 条,其左端点和右端点为 \(l_i\) 和 \(r_i\),他们也是 \(10^9\) 范围内的正整数,且一定有 \(l_i≤r_i\)。小沐同学还规定,如果一条A线段 \((a_i,b_i)\) 能匹配一条B线段 \((l_j,r_j)\),当且仅当 \(l_j≤a_i≤b_i≤r_j\)。

  现在小沐需要你判断能否为所有的A线段都指定一条与之匹配的B线段。注意,无论是A线段还是B线段,每条都只能匹配一次,且仅能匹配一次。

【输入格式】

  输入的第 1 行是一个整数 \(T\),表示数据组数。每组数据的第 1 行有两个整数 \(n,m\),分别表A类线段和B类线段的种类数。接下来 \(n\) 行,每行 3 个整数 \(a_i 、b_i 、s_i\),描述一种A类线段。接下来 \(m\) 行,每行三个整数 \(l_i 、r_i 、k_i\),描述一种B类线段。

【输出格式】

  仅输出共 \(T\) 行,每行一个字符串,若可以实现则输出 Yes,否则输出 No。

【输入输出样例】

 Input

3
2 2
1 4 2
3 5 1
1 4 2
2 5 1
3 2
1 3 1
2 4 1
3 5 1
1 3 2
2 5 1
2 2
1 2 2
1 2 1
1 2 1
1 2 2

 Output

Yes
No
Yes

【数据限制】

  对于 \(100\%\) 的数据,\(2≤N,M,s_i,k_i≤5000\)。

【来源】

  Mr.he

信息

ID
2539
难度
(无)
分类
贪心 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者