H. Рудольф и прожекторы

Codeforces

IDCF10176H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф решил заранее приготовить и расположить на сцене множество наглядных пособий. Теперь ему осталось только проверить, что сцена достаточно хорошо освещена. Сцена имеет ширину W и может быть представлена отрезком [0; W]. Над сценой закреплены N прожекторов. Каждый прожектор характеризуется координатой X, мощностью A и рассеянием B. При включении прожектора освещённость сцены изменяется следующим образом: Помогите Рудольфу определить, насколько хорошо будут освещены определённые точки сцены после включения всех прожекторов. Первая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены. Вторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов. Следующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора. Следующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость. Следующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость. Выведите M целых чисел — освещённость каждой из искомых точек. ## Входные Данные Первая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены.Вторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов.Следующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора.Следующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость.Следующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость. ## Выходные Данные Выведите M целых чисел — освещённость каждой из искомых точек. ## Примеры Входные данные1016 4 1110 1 2 3 4 5 6 7 8 9 10Выходные данные0 0 0 1 2 3 4 3 2 1 0 Входные данные1023 10 17 5 2100 1 2 3 9 8 7 6 3 4Выходные данные7 8 9 10 5 8 11 10 10 9 [samples]

**Definitions** Let $ W \in \mathbb{Z}^+ $ be the width of the stage, represented as the interval $[0, W]$. Let $ N \in \mathbb{Z}^+ $ be the number of spotlights. For each spotlight $ i \in \{1, \dots, N\} $, define: - $ x_i \in [0, W] $: position, - $ a_i \in \mathbb{Z}^+ $: power, - $ b_i \in \mathbb{Z}^+ $: spread, with $ b_i \leq a_i $. Let $ M \in \mathbb{Z}^+ $ be the number of query points. For each query point $ j \in \{1, \dots, M\} $, let $ x_j \in [0, W] $ be its coordinate. **Constraints** 1. $ 1 \leq W \leq 10^6 $ 2. $ 1 \leq N \leq 5 \cdot 10^5 $ 3. $ 0 \leq x_i \leq W $, $ 1 \leq a_i \leq 10^6 $, $ 1 \leq b_i \leq a_i $ for all $ i $ 4. $ 1 \leq M \leq 5 \cdot 10^5 $ 5. $ 0 \leq x_j \leq W $ for all $ j $ **Objective** For each query point $ x_j $, compute the total illumination: $$ I(x_j) = \sum_{\substack{i=1 \\ |x_j - x_i| \leq b_i}}^{N} \left( a_i - |x_j - x_i| \right) $$

API Response (JSON)

{
  "problem": {
    "name": "H. Рудольф и прожекторы",
    "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": "CF10176H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ W \\in \\mathbb{Z}^+ $ be the width of the stage, represented as the interval $[0, W]$.  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of spotlights.  \nFor each spotlight $ i \\in \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments