L. High Probability Cast

Codeforces

IDCF10134L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A mage knows n spells, the i-th of which, when casted, deals random damage (not necessarily integer), uniformly distributed from ai to bi. There are m monsters dwelling in the world, and to kill the j-th of them it is required to deal him at least xj damage. Unfortunately, monsters are so fast that the mage has time to cast only a single spell while fighting each of the monsters, before being killed by that monster. Which spell should be chosen to destroy each of the monsters, so that the probability of killing that monster would be maximized? The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of spells. The next n lines describe spells. Each of them contains two integers ai and bi (1 ≤ ai ≤ bi ≤ 109) — the minimal and maximal damage the i-th spell can deal. The next line contains a single integer m (1 ≤ m ≤ 200000) — the number of monsters. The next line contains m integers xj separated by a space (1 ≤ xj ≤ 109) — the minimal amount of damage required to destroy the j-th monster. Output m integers separated by a space, the j-th of which should be equal to the number of spell which should be used to destroy the j-th monster. The spells are numbered from one in the order they are listed in the input. If there are many spells which give the maximal probability of destroying some monster, you can output any of these spells. ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of spells.The next n lines describe spells. Each of them contains two integers ai and bi (1 ≤ ai ≤ bi ≤ 109) — the minimal and maximal damage the i-th spell can deal.The next line contains a single integer m (1 ≤ m ≤ 200000) — the number of monsters.The next line contains m integers xj separated by a space (1 ≤ xj ≤ 109) — the minimal amount of damage required to destroy the j-th monster. ## Output Output m integers separated by a space, the j-th of which should be equal to the number of spell which should be used to destroy the j-th monster. The spells are numbered from one in the order they are listed in the input. If there are many spells which give the maximal probability of destroying some monster, you can output any of these spells. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $. Let $ \mathcal{S} = \{ (a_i, b_i) \mid i \in \{1, \dots, n\} \} $ be the set of spells, where $ a_i, b_i \in \mathbb{R} $, $ 1 \le a_i \le b_i \le 10^9 $. Let $ \mathcal{M} = \{ x_j \mid j \in \{1, \dots, m\} \} $ be the set of monster thresholds, where $ x_j \in \mathbb{R} $, $ 1 \le x_j \le 10^9 $. For spell $ i $, the damage $ D_i \sim \text{Uniform}(a_i, b_i) $. The probability that spell $ i $ kills monster $ j $ is: $$ P_{i,j} = \begin{cases} 0 & \text{if } b_i < x_j \\ \frac{b_i - x_j}{b_i - a_i} & \text{if } a_i \le x_j \le b_i \\ 1 & \text{if } a_i \ge x_j \end{cases} $$ **Constraints** 1. $ 1 \le n \le 200000 $ 2. $ 1 \le m \le 200000 $ 3. $ 1 \le a_i \le b_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $ 4. $ 1 \le x_j \le 10^9 $ for all $ j \in \{1, \dots, m\} $ **Objective** For each monster $ j \in \{1, \dots, m\} $, find: $$ \arg\max_{i \in \{1, \dots, n\}} P_{i,j} $$ Output the index $ i $ (1-based) of any spell achieving this maximum.

API Response (JSON)

{
  "problem": {
    "name": "L. High Probability Cast",
    "description": {
      "content": "A mage knows n spells, the i-th of which, when casted, deals random damage (not necessarily integer), uniformly distributed from ai to bi. There are m monsters dwelling in the world, and to kill the j",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A mage knows n spells, the i-th of which, when casted, deals random damage (not necessarily integer), uniformly distributed from ai to bi. There are m monsters dwelling in the world, and to kill the j...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{S} = \\{ (a_i, b_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of spells, where $ a_i, b_i \\in \\mathbb{R} $, $ 1 \\le a_i \\le b_i \\le 10...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments