{"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":"Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф решил заранее приготовить и расположить на сцене множество наглядных пособий. Теперь ему осталось только проверить, что сцена достаточно хорошо освещена.\n\nСцена имеет ширину W и может быть представлена отрезком [0; W]. Над сценой закреплены N прожекторов.\n\nКаждый прожектор характеризуется координатой X, мощностью A и рассеянием B. При включении прожектора освещённость сцены изменяется следующим образом: \n\nПомогите Рудольфу определить, насколько хорошо будут освещены определённые точки сцены после включения всех прожекторов.\n\nПервая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены.\n\nВторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов.\n\nСледующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора.\n\nСледующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость.\n\nСледующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость.\n\nВыведите M целых чисел — освещённость каждой из искомых точек.\n\n## Входные Данные\n\nПервая строка содержит целое число 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) — координаты точек, для которых необходимо определить освещённость.\n\n## Выходные Данные\n\nВыведите M целых чисел — освещённость каждой из искомых точек.\n\n## Примеры\n\nВходные данные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 \n\n[samples]","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, \\dots, N\\} $, define:  \n- $ x_i \\in [0, W] $: position,  \n- $ a_i \\in \\mathbb{Z}^+ $: power,  \n- $ b_i \\in \\mathbb{Z}^+ $: spread, with $ b_i \\leq a_i $.  \n\nLet $ M \\in \\mathbb{Z}^+ $ be the number of query points.  \nFor each query point $ j \\in \\{1, \\dots, M\\} $, let $ x_j \\in [0, W] $ be its coordinate.\n\n**Constraints**  \n1. $ 1 \\leq W \\leq 10^6 $  \n2. $ 1 \\leq N \\leq 5 \\cdot 10^5 $  \n3. $ 0 \\leq x_i \\leq W $, $ 1 \\leq a_i \\leq 10^6 $, $ 1 \\leq b_i \\leq a_i $ for all $ i $  \n4. $ 1 \\leq M \\leq 5 \\cdot 10^5 $  \n5. $ 0 \\leq x_j \\leq W $ for all $ j $\n\n**Objective**  \nFor each query point $ x_j $, compute the total illumination:  \n$$\nI(x_j) = \\sum_{\\substack{i=1 \\\\ |x_j - x_i| \\leq b_i}}^{N} \\left( a_i - |x_j - x_i| \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10176H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}