English · Original
Chinese · Translation
Formal · Original
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_.
## Input
The first line contains one integer _n_ (1 ≤ _n_ ≤ 3·105) — the number of segments.
Each of the next _n_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ 109) — the _i_\-th segment.
## Output
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_.
[samples]
## Note
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.
你被给定一个一维线段序列 #cf_span[a1, a2, ..., an]，编号从 #cf_span[1] 到 #cf_span[n]。你的任务是找到两个不同的索引 #cf_span[i] 和 #cf_span[j]，使得线段 #cf_span[ai] 包含于线段 #cf_span[aj] 中。
线段 #cf_span[[l1, r1]] 包含于线段 #cf_span[[l2, r2]] 当且仅当 #cf_span[l1 ≥ l2] 且 #cf_span[r1 ≤ r2]。
请输出索引 #cf_span[i] 和 #cf_span[j]。如果存在多个答案，输出任意一个即可。如果无解，请输出 _-1 -1_。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 线段的数量。
接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ 109]) —— 第 #cf_span[i] 个线段。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105]) —— 线段的数量。接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ 109]) —— 第 #cf_span[i] 个线段。
## Output
请输出两个不同的索引 #cf_span[i] 和 #cf_span[j]，使得线段 #cf_span[ai] 包含于线段 #cf_span[aj] 中。如果存在多个答案，输出任意一个即可。如果无解，请输出 _-1 -1_。
[samples]
## Note
在第一个例子中，以下配对均被视为正确：
#cf_span[(2, 1), (3, 1), (4, 1), (5, 1)] —— 甚至不接触边界；
#cf_span[(3, 2), (4, 2), (3, 5), (4, 5)] —— 接触一个边界；
#cf_span[(5, 2), (2, 5)] —— 完全重合。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of segments.
Let $ S = \{(l_i, r_i, i) \mid i \in \{1, \dots, n\}\} $ be the set of segments, where each segment is represented by its left endpoint $ l_i $, right endpoint $ r_i $, and its 1-based index $ i $.
**Constraints**
1. $ 1 \leq n \leq 3 \cdot 10^5 $
2. For each $ i \in \{1, \dots, n\} $: $ 1 \leq l_i \leq r_i \leq 10^9 $
**Objective**
Find two distinct indices $ i, j \in \{1, \dots, n\} $, $ i \ne j $, such that:
$$
l_i \geq l_j \quad \text{and} \quad r_i \leq r_j
$$
If such a pair exists, output $ (i, j) $.
If no such pair exists, output $ (-1, -1) $.
API Response (JSON)
{
"problem": {
"name": "C. Nested Segments",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF976C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个一维线段序列 #cf_span[a1, a2, ..., an]，编号从 #cf_span[1] 到 #cf_span[n]。你的任务是找到两个不同的索引 #cf_span[i] 和 #cf_span[j]，使得线段 #cf_span[ai] 包含于线段 #cf_span[aj] 中。\n\n线段 #cf_span[[l1, r1]] 包含于线段 #cf_span[[l2, r2]] 当且...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of segments. \nLet $ S = \\{(l_i, r_i, i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of segments, where each segment is represented by its left e...",
"is_translate": false,
"language": "Formal"
}
]
}