3772 - Joc Cu Lasere

Cerinţa

RAU-Gigel testează un joc cu trageri și premii. Jocul constă într-o serie de acțiuni care au loc la anumite momente de timp. Acțiunile pot fi: (1) aparițiile unor premii sau (2) trageri. Premiile apar la anumite înălțimi, pentru un interval de timp bine definit. Tragerile au loc la anumite momente de timp și se propagă în spațiu instantaneu. RAU-Gigel câștigă câte un punct pentru fiecare premiu ochit.

Din păcate, RAU-Gigel nu și-a calibrat bine trăgătorul, astfel încât fiecare tragere devine activă numai între două înălțimi date: [h1, h2], interval numit rază de acțiune. Așadar, RAU-Gigel nu va câștiga puncte decât pentru premiile aflate în raza de acțiune a fiecărei trageri.

Dacă o tragere are loc exact în același moment în care apare un premiu în raza ei de acțiune, acesta se consideră ”ochit”. Similar, dacă un premiu este programat să dispară la un moment de timp în care are loc o tragere, iar el se află în raza de acțiune a tragerii, atunci punctul se consideră câștigat. Un premiu ochit rămâne în joc și poate genera și alte puncte, până la momentul la care este programat să dispară. Nu pot avea loc două trageri în același moment, dar pot exista mai multe premii la aceeași înălțime în același timp și toate sunt generatoare de puncte.

Dându-se numărul N de operații de tipul 1 sau 2, unde:

Operația 1 t d h – reprezintă un premiu: t este momentul în care apare, d este numărul de unități de timp cât este programat să existe, iar h este înălțimea la care apare; Operația 2 t h1 h2 – reprezintă o tragere, t este momentul în care are loc, iar h1 și h2 reprezintă înălțimile în care tragerea este activă (raza de acțiune). Să se afle câte puncte câștigă RAU-Gigel la fiecare tragere și care este punctajul cu care termină jocul?

Date de intrare

Fișierul de intrare lasere.in conține pe prima linie un număr natural N. Pe următoarele N linii se află operațiile, în ordine crescătoare a momentului t de începere a acțiunii, de tipul 1 și 2, de forma:

• 1 t d h , unde t, d, h sunt 3 numere naturale separate cu un spațiu, cu semnificația de mai sus, reprezintă o operație de tipul 1;
• 2 t h1 h2 , unde t, h1, h2 sunt 3 numere naturale separate cu un spațiu, cu semnificația de mai sus, reprezintă o operație de tipul 2.

Date de ieșire

Fișierul de ieșire lasere.out va conține răspunsurile, în ordinea solicitării, pentru operațiile de tip 2, câte unul pe linie, iar pe ultimul rând, punctajul lui RAU-Gigel la sfârșitul jocului.

Restricţii şi precizări

• 2 ≤ N ≤ 100.000
• 1 ≤ t, d, h, h1, h2 ≤ 1.000.000.000, h1<h2

Exemplul 1

lasere.in

4
1 2 8 4
2 3 5 10
1 5 6 7
2 8 3 8

lasere.out

0
2
2

Explicație

Sunt 4 acțiuni, dintre care 2 trageri (tipul 2). La prima tragere RAU-Gigel nu nimerește singurul premiu existent în momentul tragerii (momentul 3), pentru că aceasta nu este în raza sa de acțiune.

La a doua tragere, din momentul 8, RAU-Gigel nimerește ambele premii.

Total: 0+2=2.

Exemplul 2

lasere.in

6
2 2 4 5
1 2 8 4
2 3 5 10
1 5 6 7
2 10 4 8
1 10 3 7

lasere.out

1
0
3
4

Explicație

Sunt 6 acțiuni, dintre care 3 trageri. În momentul 2 au loc 2 acțiuni: o tragere și apariția unui premiu. Pentru că premiul, aflat la înălțimea 4, este în raza de acțiune a acestei trageri și anume în intervalul [4-5], RAU-Gigel câștigă un punct.

La a doua tragere, nu nimerește nimic, singurul premiu existent în acel moment nefiind în raza sa de acțiune.

La a treia tragere, RAU-Gigel mai câștigă 3 puncte, acele premii fiind în raza de acțiune a tragerii (intervalul 4-8). Se numără inclusiv primul premiu, planificat să existe până în momentul 10, care este și momentul tragerii. De asemenea, se numără și ultimul premiu, apărut chiar în momentul tragerii.

Total: 1+0+3=4.

Rezolvare

<syntaxhighlight lang="python" line> def main():

   n = int(input())
   actions = []
   for _ in range(n):
       action = list(map(int, input().split()))
       actions.append(action)
   
   # Dicționar pentru stocarea premiilor și tragerilor
   prizes = {}
   shots = []
   
   # Parcurgem toate acțiunile și le salvăm în dicționarul corespunzător
   for action in actions:
       if action[0] == 1:  # Dacă este o acțiune de tip premiu
           start_time = action[1]
           end_time = action[1] + action[2]  # Momentul în care premiul va dispărea
           height = action[3]
           prizes[start_time] = (end_time, height)
       elif action[0] == 2:  # Dacă este o acțiune de tip tragere
           time = action[1]
           height1 = action[2]
           height2 = action[3]
           shots.append((time, height1, height2))
   
   # Parcurgem fiecare tragere și numărăm câte premii sunt în raza de acțiune
   for shot in shots:
       time = shot[0]
       height1 = shot[1]
       height2 = shot[2]
       points = 0
       for prize_time, prize_info in prizes.items():
           if time >= prize_time and time <= prize_info[0] and prize_info[1] >= height1 and prize_info[1] <= height2:
               points += 1
       print(points)

if __name__ == "__main__":

   main()

</syntaxhighlight>