AT_aalc001_p.Connect the Dots
省选/NOI-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
圆上有 2N 个顶点,按顺时针顺序依次编号为顶点 1、顶点 2、…、顶点 2N。
给定一个由 N 个整数对组成的序列 ((A1,B1),(A2,B2),…,(AN,BN))。这 2N 个值 A1,…,AN,B1,…,BN 互不相同。
处理 Q 个查询。在第 j 个查询中,给出整数 lj,rj。判断是否能画出满足以下所有条件的曲线:
- 对每个 i=lj,lj+1,…,rj,画出一条连接顶点 Ai 和顶点 Bi 的曲线;
- 每条曲线均位于圆内或圆周上;
- 任意两条不同的曲线互不相交。
每个查询相互独立。一个查询中所画的曲线不影响其他查询。
输入格式
输入从标准输入中按以下格式给出:
N Q
A1 B1
A2 B2
⋮
AN BN
l1 r1
l2 r2
⋮
lQ rQ
输出格式
输出 Q 行。
在第 j 行中,如果能够为第 j 个查询绘制满足条件的曲线,则输出 Yes,否则输出 No。
输入输出样例
输入#1
5 6 1 10 2 5 3 4 6 8 7 9 1 3 2 4 4 5 1 5 3 3 3 4
输出#1
Yes Yes No No Yes Yes
输入#2
4 4 1 5 2 6 3 4 7 8 1 2 2 4 1 3 3 4
输出#2
No Yes No Yes
说明/提示
样例 1 解释:
对于查询 1,可以画出连接顶点 1 与 10、顶点 2 与 5、以及顶点 3 与 4 的曲线,且这些曲线互不相交。
对于查询 3,连接顶点 6 与 8 的曲线和连接顶点 7 与 9 的曲线无法在不相交的情况下画出。
约束条件
- 2≤N≤2×105
- 1≤Q≤2×105
- 1≤Ai<Bi≤2N
- (A1,…,AN,B1,…,BN) 是 (1,2,…,2N) 的一个排列。
- 1≤lj≤rj≤N
- 输入中的所有数值均为整数。
输入解题思路,AI测评打分。不知道怎么写?