题目详情题解（0）讨论（0）提交记录（0）

AT_abc424_f.[ABC424F] Adding Chords

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个圆上等间隔地标有 NN 个点，顺时针编号为 1,2,…,N1,2,\dots,N。

现在给你 QQ 个询问，请依次处理。

  • 画一条连接第 AiA_i 个点和第 BiB_i 个点的线段。如果该线段与之前已经画过的任意一条线段相交，则不画这条线段。

这里保证 2Q2Q 个整数 A1,…,AQ,B1,…,BQA_1,\ldots,A_Q,B_1,\ldots,B_Q 两两不同。

对于每个询问，回答该线段是否被画出。

输入格式

输入由标准输入提供，格式如下：

N QN\ Q
A1 B1A_1\ B_1
A2 B2A_2\ B_2
⋮\vdots
AQ BQA_Q\ B_Q

输出格式

输出共 QQ 行。对于第 ii 个询问，如果第 ii 条线段被画出，则输出 Yes，否则输出 No。

输入输出样例

  • 输入#1

    8 3
1 5
2 7
3 4

    输出#1

    Yes
No
Yes

  • 输入#2

    999999 4
123456 987654
888888 999999
1 3
2 777777

    输出#2

    Yes
No
Yes
No

说明/提示

样例解释 1

按照输入的询问，线段的绘制如图所示。

  • 第 11 次询问，连接点 11 和点 55 的线段被画出。
  • 第 22 次询问，连接点 22 和点 77 的线段由于与第 11 次询问画出的线段相交，因此没有被画出。
  • 第 33 次询问，连接点 33 和点 44 的线段被画出。

数据范围

  • 2≤N≤1062 \leq N \leq 10^6
  • 1≤Q≤3×1051 \leq Q \leq 3\times 10^5
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • 2Q2Q 个整数 A1,…,AQ,B1,…,BQA_1,\ldots,A_Q,B_1,\ldots,B_Q 互不相同。
  • 所有输入值为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页