| Fişierul intrare/ieşire: | inspiratie.in, inspiratie.out | Sursă | ONI 2026, Baraj Seniori, ziua 1 |
| Autor | Alexandru Lorintz | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Inspiratie
Înainte să moară Freddie Mercury m-a sunat pe mine şi mi-a zis aşa: "Lorintz, schimbă şi tu enunţul ăsta în memoria mea!".
Oraşul Piteşti este reprezentat în plan unde punctul (0,0) este restaurantul Ottoman (informaţie relevantă doar în scop turistic). Comisia ştiinţifică de la ONI 2026 este formată din N membri, iar pentru fiecare membru k primim un triplet de forma (xk, yk, vk), reprezentând faptul că membrul k se află la punctul de coordonate (xk, yk) şi are o valoare vk (valoare cu care te naşti).
Membrii comisiei sunt lipsiţi de ocupaţie şi vor să inspire orice concurent care se află în proximitatea lor. Orice concurent care se află la distanţă Manhattan D de membrul k din comisie (cu D < vk) este inspirat de către acesta, primind astfel vk - D unităţi de talent. Dacă un concurent se află în aria de inspiraţie a mai multor membri din comisie, acesta o să acumuleze toate unităţile de talent de la fiecare astfel de membru prin adunarea acestora.
La ONI 2026 participă Q concurenţi, iar pentru fiecare concurent se ştie coordonata (x, y) în care acesta a decis să se plaseze.
Cerinţă
Pentru fiecare concurent, să se afle cantitatea totală de talent pe care a primit-o de la toţi membrii comisiei.
Date de intrare
Fişierul de intrare inspiratie.in conţine pe prima linie numerele N, Q, separate prin câte un spaţiu. Pe următoarele N linii se vor afla câte trei numere: xi, yi şi vi, reprezentând coordonatele la care se afla membrul din comisie i şi valoarea lui vi. Pe următoarele Q linii se vor afla câte două numere: xi şi yi, reprezentând coordonatele la care se plasează concurentul i.
Date de ieşire
Fişierul de ieşire inspiratie.out va conţine pe o singură linie Q numere naturale, separate prin câte un spaţiu. Al i-lea număr reprezintă cantitatea de talent pe care concurentul i o primeşte.
Restricţii
- 1 ≤ N, Q ≤ 100 000
- 1 ≤ xi, yi ≤ 108
- 1 ≤ vi ≤ 108
- Distanţa Manhattan dintre două puncte (x1, y1) şi (x2, y2) este |x1 - x2| + |y1 - y2|.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 8 | 1 ≤ N, Q ≤ 5 000, xi, yi ≤ 1 000 |
| 2 | 11 | 1 ≤ N, Q ≤ 70 000, xi, yi ≤ 1 000, vi ≤ 1 000 |
| 3 | 29 | 1 ≤ N, Q ≤ 70 000, xi, yi ≤ 1 000 |
| 4 | 34 | 1 ≤ N, Q ≤ 70 000 |
| 5 | 18 | Fără alte restricţii |
Exemplu
| inspiratie.in | inspiratie.out |
|---|---|
| 2 2 3 3 3 5 4 2 3 4 4 4 | 2 2 |
Explicaţie
Avem N=2 membri de comisie şi Q=2 concurenţi. Primul membru de comisie se află la punctul de coordonate (3, 3) cu valoarea 3, iar al doilea la punctul de coordonate (5, 4) cu valoarea 2.
- Primul concurent este la punctul (3, 4). Distanţa faţă de primul membru de comisie: |3 - 3| + |4 - 3| = 1 < 3 ⟹ talent 3 - 1 = 2. Distanţa faţă de al doilea membru de comisie: |3 - 5| + |4 - 4| = 2 ≮ 2 ⟹ talent 0. Talent total: 2.
- Al doilea concurent este la (4, 4). Distanţa faţă de primul membru de comisie: |4 - 3| + |4 - 3| = 2 < 3 ⟹ talent 3 - 2 = 1. Distanţa faţă de al doilea membru de comisie: |4 - 5| + |4 - 4| = 1 < 2 ⟹ talent 2 - 1 = 1. Talent total: 1 + 1 = 2.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
