E. Ваня и параллельные миры

Codeforces

IDCF10218E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить максимальное число тетрадей, которые можно купить, для одного мира, ему требуется решить эту задачу для $m$ миров. К счастью, отличие всех миров заключается только в том, сколько денег есть у Вани, тогда как цены в магазинах и количество доступных для покупки тетрадей во всех мирах одинаковы. *Обратите внимание, что ограничения на $a_i$ и $b_i$ отличаются от ограничений в задаче $C$!* Помогите Ване справиться с новыми трудностями! В первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно. Во второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$). В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно. Выведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире. ## Входные Данные В первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно.Во второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно. ## Выходные Данные Выведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире. ## Пример Входные данные2 3 10 30 20 8 2 5 2 Выходные данные2 4 3 [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of dictionary words. Let $ S = (s_1, s_2, \dots, s_N) $ be the dictionary, where each $ s_j $ is a string over $ \Sigma = \{a, b, \dots, z\} $. Let $ M \in \mathbb{Z} $ be the number of text words. Let $ T = (t_1, t_2, \dots, t_M) $ be the text, where each $ t_i $ is a string over $ \Sigma $. A word $ t_i \in T $ is an *abbreviation* of a dictionary word $ s_j \in S $ if $ t_i $ is a subsequence of $ s_j $ and $ |t_i| < |s_j| $. **Constraints** 1. $ 1 \leq N \leq 500 $ 2. $ \sum_{j=1}^N |s_j| \leq 2 \times 10^6 $ 3. $ 1 \leq M \leq 2000 $ 4. $ 1 \leq |t_i| \leq 10 $ for all $ i \in \{1, \dots, M\} $ 5. All strings consist only of lowercase Latin letters. 6. For each $ t_i $, there is at most one $ s_j \in S $ such that $ t_i $ is an abbreviation of $ s_j $. **Objective** For each $ i \in \{1, \dots, M\} $: - If $ t_i $ is an abbreviation of some $ s_j \in S $, output $ s_j $. - Otherwise, output $ t_i $.

API Response (JSON)

{
  "problem": {
    "name": "E. Ваня и параллельные миры",
    "description": {
      "content": "В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить макси",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10218E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить макси...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of dictionary words.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the dictionary, where each $ s_j $ is a string over $ \\Sigma = \\{a, b, \\dots, z\\} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments