A11688. Nested Segments
编程题
普及/提高-
知识点
题目描述
You are given a sequence $a_{1},a_{2},...,a_{n}$ of one-dimensional segments numbered $1$ through $n$ . Your task is to find two distinct indices $i$ and $j$ such that segment $a_{i}$ lies within segment $a_{j}$ .
Segment $[l_{1},r_{1}]$ lies within segment $[l_{2},r_{2}]$ iff $l_{1}>=l_{2}$ and $r_{1}<=r_{2}$ .
Print indices $i$ and $j$ . If there are multiple answers, print any of them. If no answer exists, print -1 -1.
给你一个由编号为 1 到 n 的一维线段组成的序列 a1, a2, ..., an 。您的任务是找到两个不同的索引 i 和 j ，使得线段 ai 位于线段 aj 中。
如果有 l1 ≥ l2 和 r1 ≤ r2 ，那么线段 [l1, r1] 位于线段 [l2, r2] 中。
打印索引 i 和 j 。如果有多个答案，则打印任意一个。如果没有答案，则打印 -1 -1.
Segment $[l_{1},r_{1}]$ lies within segment $[l_{2},r_{2}]$ iff $l_{1}>=l_{2}$ and $r_{1}<=r_{2}$ .
Print indices $i$ and $j$ . If there are multiple answers, print any of them. If no answer exists, print -1 -1.
给你一个由编号为 1 到 n 的一维线段组成的序列 a1, a2, ..., an 。您的任务是找到两个不同的索引 i 和 j ，使得线段 ai 位于线段 aj 中。
如果有 l1 ≥ l2 和 r1 ≤ r2 ，那么线段 [l1, r1] 位于线段 [l2, r2] 中。
打印索引 i 和 j 。如果有多个答案，则打印任意一个。如果没有答案，则打印 -1 -1.
输入格式
The first line contains one integer $n$ ( $1<=n<=3·10^{5}$ ) — the number of segments.
Each of the next $n$ lines contains two integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=10^{9}$ ) — the $i$ -th segment.
输入
第一行包含一个整数 $n ( 1 ≤ n ≤ 3·10^5 )$ - 片段数。
接下来的每 n 行包含两个整数 li 和 ri $( 1 ≤ li ≤ ri ≤ 10^9 )$ - 第 i 个线段
Each of the next $n$ lines contains two integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=10^{9}$ ) — the $i$ -th segment.
输入
第一行包含一个整数 $n ( 1 ≤ n ≤ 3·10^5 )$ - 片段数。
接下来的每 n 行包含两个整数 li 和 ri $( 1 ≤ li ≤ ri ≤ 10^9 )$ - 第 i 个线段
输出格式
Print two distinct indices $i$ and $j$ such that segment $a_{i}$ lies within segment $a_{j}$ . If there are multiple answers, print any of them. If no answer exists, print -1 -1.
输出
打印两个不同的索引 i 和 j ，使得线段 ai 位于线段 aj 中。如果有多个答案，则打印任意一个。如果没有答案，则打印 -1 -1 。
输出
打印两个不同的索引 i 和 j ，使得线段 ai 位于线段 aj 中。如果有多个答案，则打印任意一个。如果没有答案，则打印 -1 -1 。
输入输出样例
输入 #1
5 1 10 2 9 3 9 2 3 2 9
输出 #1
2 1
输入 #2
3 1 5 2 6 6 20
输出 #2
-1 -1
说明/提示
In the first example the following pairs are considered correct:
- $(2,1),(3,1),(4,1),(5,1)$ — not even touching borders;
- $(3,2),(4,2),(3,5),(4,5)$ — touch one border;
- $(5,2),(2,5)$ — match exactly.
注意
在第一个示例中，下列配对被认为是正确的：
(2, 1), (3, 1), (4, 1), (5, 1) - 甚至没有接触到边框；
(3, 2), (4, 2), (3, 5), (4, 5) - 接触到一个边框；
(5, 2), (2, 5) - 完全匹配。
- $(2,1),(3,1),(4,1),(5,1)$ — not even touching borders;
- $(3,2),(4,2),(3,5),(4,5)$ — touch one border;
- $(5,2),(2,5)$ — match exactly.
注意
在第一个示例中，下列配对被认为是正确的：
(2, 1), (3, 1), (4, 1), (5, 1) - 甚至没有接触到边框；
(3, 2), (4, 2), (3, 5), (4, 5) - 接触到一个边框；
(5, 2), (2, 5) - 完全匹配。