D. Fedor and coupons

Codeforces

IDCF754D

Time4000ms

Memory256MB

Difficulty—

binary searchdata structuresgreedysortings

English · Original

Chinese · Translation

Formal · Original

All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has _n_ discount coupons, the _i_\-th of them can be used with products with ids ranging from _l__i_ to _r__i_, inclusive. Today Fedor wants to take exactly _k_ coupons with him. Fedor wants to choose the _k_ coupons in such a way that the number of such products _x_ that all coupons can be used with this product _x_ is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor! ## Input The first line contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 3·105) — the number of coupons Fedor has, and the number of coupons he wants to choose. Each of the next _n_ lines contains two integers _l__i_ and _r__i_ ( - 109 ≤ _l__i_ ≤ _r__i_ ≤ 109) — the description of the _i_\-th coupon. The coupons can be equal. ## Output In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted. In the second line print _k_ distinct integers _p_1, _p_2, ..., _p__k_ (1 ≤ _p__i_ ≤ _n_) — the ids of the coupons which Fedor should choose. If there are multiple answers, print any of them. [samples] ## Note In the first example if we take the first two coupons then all the products with ids in range \[40, 70\] can be bought with both coupons. There are 31 products in total. In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

我们所有的角色都有爱好，费多尔也不例外。他喜欢去附近的超市购物。超市中的商品具有唯一的整数编号，并且对于每个整数，都存在一个编号等于该整数的商品。费多尔有 #cf_span[n] 张折扣券，第 #cf_span[i] 张券可用于编号在 #cf_span[li] 到 #cf_span[ri]（包含两端）之间的商品。今天费多尔想恰好带 #cf_span[k] 张券。费多尔希望选择 #cf_span[k] 张券，使得所有券都能使用的商品编号 #cf_span[x] 的数量尽可能大（更直观的理解请见示例）。费多尔也希望节省时间，因此他请你帮他选择券。请帮助费多尔！第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 3·105]）——费多尔拥有的券数和他想选择的券数。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[ - 109 ≤ li ≤ ri ≤ 109]）——描述第 #cf_span[i] 张券。券可能相同。第一行输出一个整数——所有选中的券都能使用的商品的最大数量。那些至少有一张券不能使用的商品不应被计入。第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[p1, p2, ..., pk]（#cf_span[1 ≤ pi ≤ n]）——费多尔应选择的券的编号。如果有多个答案，输出任意一个即可。在第一个例子中，如果我们选取前两张券，则所有编号在 #cf_span[[40, 70]] 范围内的商品都可以用这两张券购买。总共有 #cf_span[31] 个商品。在第二个例子中，没有任何商品能同时被两张券使用，因此答案是 #cf_span[0]。在这个例子中，费多尔可以任选两张券。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 3·105]）——费多尔拥有的券数和他想选择的券数。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[ - 109 ≤ li ≤ ri ≤ 109]）——描述第 #cf_span[i] 张券。券可能相同。 ## Output 第一行输出一个整数——所有选中的券都能使用的商品的最大数量。那些至少有一张券不能使用的商品不应被计入。第二行输出 #cf_span[k] 个互不相同的整数 #cf_span[p1, p2, ..., pk]（#cf_span[1 ≤ pi ≤ n]）——费多尔应选择的券的编号。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个例子中，如果我们选取前两张券，则所有编号在 #cf_span[[40, 70]] 范围内的商品都可以用这两张券购买。总共有 #cf_span[31] 个商品。在第二个例子中，没有任何商品能同时被两张券使用，因此答案是 #cf_span[0]。费多尔可以任选两张券。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 3 \cdot 10^5 $. Let $ C = \{ (l_i, r_i) \mid i \in \{1, \dots, n\} \} $ be a set of $ n $ intervals, where $ l_i, r_i \in \mathbb{Z} $ and $ l_i \leq r_i $. **Constraints** For all $ i \in \{1, \dots, n\} $: $ -10^9 \leq l_i \leq r_i \leq 10^9 $ **Objective** Choose a subset $ S \subseteq C $ with $ |S| = k $ such that the intersection $ \bigcap_{(l_i, r_i) \in S} [l_i, r_i] $ has maximum possible cardinality (i.e., number of integer points). Let $ I_S = [\max_{i \in S} l_i, \min_{i \in S} r_i] $. Maximize $ |I_S| = \max(0, \min_{i \in S} r_i - \max_{i \in S} l_i + 1) $. Output: 1. The maximum value of $ |I_S| $. 2. A set of $ k $ distinct indices $ \{p_1, \dots, p_k\} \subseteq \{1, \dots, n\} $ corresponding to the chosen coupons.

Samples

Input #1

Output #1

31
1 2

Input #2

Output #2

0
1 2

Input #3

Output #3

21
3 4

API Response (JSON)

{
  "problem": {
    "name": "D. Fedor and coupons",
    "description": {
      "content": "All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. The goods in the supermarket have unique integer ids. Also, for every integer there is ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF754D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket.\n\nThe goods in the supermarket have unique integer ids. Also, for every integer there is ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们所有的角色都有爱好，费多尔也不例外。他喜欢去附近的超市购物。\n\n超市中的商品具有唯一的整数编号，并且对于每个整数，都存在一个编号等于该整数的商品。费多尔有 #cf_span[n] 张折扣券，第 #cf_span[i] 张券可用于编号在 #cf_span[li] 到 #cf_span[ri]（包含两端）之间的商品。今天费多尔想恰好带 #cf_span[k] 张券。\n\n费多尔希望选择 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 3 \\cdot 10^5 $.  \nLet $ C = \\{ (l_i, r_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of $ n $ intervals, where $ l_i, r_i \\in \\m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments