E. Turn Off The TV

Codeforces

IDCF863E

Time2000ms

Memory256MB

Difficulty—

data structuressortings

English · Original

Chinese · Translation

Formal · Original

Luba needs your help again! Luba has _n_ TV sets. She knows that _i_\-th TV set will be working from moment of time _l__i_ till moment _r__i_, inclusive. Luba wants to switch off one of TV sets in order to free the socket. Let's call some TV set _redundant_ if after switching it off the number of **integer** moments of time when at least one of TV sets is working won't decrease. Luba will be very upset if she has to switch off a non-_redundant_ TV set. Help Luba by telling her the index of some _redundant_ TV set. If there is no any, print _\-1_. ## Input The first line contains one integer number _n_ (1 ≤ _n_ ≤ 2·105) — the number of TV sets. Then _n_ lines follow, each of them containing two integer numbers _l__i_, _r__i_ (0 ≤ _l__i_ ≤ _r__i_ ≤ 109) denoting the working time of _i_\-th TV set. ## Output If there is no any redundant TV set, print _\-1_. Otherwise print the index of any redundant TV set (TV sets are indexed from 1 to _n_). If there are multiple answers, print any of them. [samples] ## Note Consider the first sample. Initially all integer moments of time such that at least one TV set is working are from the segment \[1;7\]. It's easy to see that this segment won't change if we switch off the first TV set (or the second one). Note that in the fourth sample you can switch off the second TV set, since even without it all integer moments such that any of the TV sets is working denote the segment \[1;4\].

Luba 再次需要你的帮助！Luba 有 #cf_span[n] 台电视。她知道第 #cf_span[i] 台电视将在时间点 #cf_span[li] 到 #cf_span[ri]（包含两端）期间工作。 Luba 想要关闭其中一台电视以腾出插座。我们称某台电视为 _冗余_ 的，如果关闭它之后，至少有一台电视工作的 _整数_ 时间点的数量不会减少。如果 Luba 必须关闭一台非 _冗余_ 的电视，她会非常难过。请帮助 Luba，告诉她某台 _冗余_ 电视的编号。如果没有这样的电视，请输出 _-1_。第一行包含一个整数 #cf_span[n (1 ≤ n ≤ 2·105)] —— 电视的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[li, ri (0 ≤ li ≤ ri ≤ 109)]，表示第 #cf_span[i] 台电视的工作时间区间。如果没有冗余电视，请输出 _-1_。否则，请输出任意一台冗余电视的编号（电视编号从 1 到 #cf_span[n]）。如果有多个答案，输出任意一个即可。考虑第一个样例。最初，至少有一台电视工作的所有整数时间点构成区间 #cf_span[[1;7]]。可以很容易看出，如果关闭第一台电视（或第二台电视），这个区间不会改变。注意，在第四个样例中，你可以关闭第二台电视，因为即使没有它，所有有电视工作的整数时间点仍然构成区间 #cf_span[[1;4]]。 ## Input 第一行包含一个整数 #cf_span[n (1 ≤ n ≤ 2·105)] —— 电视的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[li, ri (0 ≤ li ≤ ri ≤ 109)]，表示第 #cf_span[i] 台电视的工作时间区间。 ## Output 如果没有冗余电视，请输出 _-1_。否则，请输出任意一台冗余电视的编号（电视编号从 1 到 #cf_span[n]）。如果有多个答案，输出任意一个即可。 [samples] ## Note 考虑第一个样例。最初，至少有一台电视工作的所有整数时间点构成区间 #cf_span[[1;7]]。可以很容易看出，如果关闭第一台电视（或第二台电视），这个区间不会改变。注意，在第四个样例中，你可以关闭第二台电视，因为即使没有它，所有有电视工作的整数时间点仍然构成区间 #cf_span[[1;4]]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of TV sets. For each $ i \in \{1, \dots, n\} $, let $ I_i = [l_i, r_i] \subseteq \mathbb{Z} $ be the closed interval of integer time moments during which the $ i $-th TV set is working. Let $ U = \bigcup_{i=1}^n I_i $ be the union of all intervals. A TV set $ k $ is **redundant** if $ \bigcup_{i \neq k} I_i = U $. **Constraints** 1. $ 1 \le n \le 2 \cdot 10^5 $ 2. $ 0 \le l_i \le r_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find any index $ k \in \{1, \dots, n\} $ such that $ \bigcup_{i \neq k} I_i = U $. If no such $ k $ exists, output $ -1 $.

Samples

Input #1

Output #1

Input #2

2
0 10
0 10

Output #2

Input #3

Output #3

\-1

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "E. Turn Off The TV",
    "description": {
      "content": "Luba needs your help again! Luba has _n_ TV sets. She knows that _i_\\-th TV set will be working from moment of time _l__i_ till moment _r__i_, inclusive. Luba wants to switch off one of TV sets in or",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF863E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Luba needs your help again! Luba has _n_ TV sets. She knows that _i_\\-th TV set will be working from moment of time _l__i_ till moment _r__i_, inclusive.\n\nLuba wants to switch off one of TV sets in or...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Luba 再次需要你的帮助！Luba 有 #cf_span[n] 台电视。她知道第 #cf_span[i] 台电视将在时间点 #cf_span[li] 到 #cf_span[ri]（包含两端）期间工作。\n\nLuba 想要关闭其中一台电视以腾出插座。我们称某台电视为 _冗余_ 的，如果关闭它之后，至少有一台电视工作的 _整数_ 时间点的数量不会减少。如果 Luba 必须关闭一台非 _冗余_ 的电视，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of TV sets.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ I_i = [l_i, r_i] \\subseteq \\mathbb{Z} $ be the closed interval of integer time moment...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments