3540 - Ambuscada

Cerința

N soldați, numerotați de la 1 la N, sunt prinși într-o ambuscadă. Asupra lor se execută M atacuri de tun. Atacurile afectează nu doar un soldat, ci un interval de soldați, provocând fiecăruia dintre aceștia o anumită pierdere (damage). De exemplu, atacul (3,7,5) afectează soldații 3,4,5,6,7 cu 5 damage. La început, toți soldații au V vieți. Câți soldați rămân în viață după cele M atacuri?

Date de intrare

Fișierul de intrare ambuscada.in conține pe prima linie numerele naturale N, M și V separate prin spații. Pe următoarele M linii se află câte 3 numere naturale i j k separate cu un spațiu, cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire ambuscada.out va conține un singur număr natural reprezentând numărul de soldați rămași în viață.

Restricții și precizări

• 2 ≤ N ≤ 1.000.000.000, 1 ≤ M ≤ 100.000, 1 ≤ V ≤ 1.000.000.000
• In toate testele, 1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ V
• Pentru teste în valoare de 30 de puncte, N<=100.000 și M<=50

Exemplul 1

ambuscada.in

6 4 10

2 5 2

1 3 7

2 6 3

3 5 6

ambuscada.out

2

Explicație

Inițial toți soldații aveau 10 vieți. După prima tragere: 10 8 8 8 8 10 După a doua tragere: 3 1 1 8 8 10 După a treia tragere: 3 0 0 5 5 7 După a patra tragere: 3 0 0 0 0 7 In final, 2 soldați au rămas în viață: primul și ultimul.

Exemplul 2

ambuscada.in

5 2

2 7 8

1

ambuscada.out

Date invalide: Linia 1 nu contine suficiente valori

Rezolvare

#3540 Ambuscada
def verificare_date_intrare(N, M, V, atacuri):
  # Verificăm dacă N, M și V sunt în intervalul specificat
  if not (2 <= N <= 1000000000 and 1 <= M <= 100000 and 1 <= V <= 1000000000):
    return False
  
  # Verificăm fiecare atac
  for atac in atacuri:
    i, j, k = atac
    # Verificăm dacă i, j și k sunt în intervalul specificat
    if not (1 <= i <= j <= N and 1 <= k <= V):
      return False
  
  return True

def soldati_ramasii(N, M, V, atacuri):
  # Inițializăm un vector cu viețile soldaților
  soldati = [V] * N
  
  # Parcurgem fiecare atac și actualizăm starea soldaților afectați
  for atac in atacuri:
    i, j, k = atac
    for index in range(i-1, j):
      soldati[index] -= k
  
  # Numărăm câți soldați au vieți pozitive și returnăm rezultatul
  soldati_ramas = sum(1 for viata in soldati if viata > 0)
  return soldati_ramas

def main():
  # Citim datele de intrare din fișier
  with open('ambuscada.in', 'r') as f:
    linii = f.readlines()
  
  # Verificăm dacă există suficiente linii în fișierul de intrare
  if len(linii) < 2:
    # Scriem mesaj de date invalide în fișierul de ieșire
    with open('ambuscada.out', 'w') as f:
      f.write("Date invalide: Nu sunt suficiente date in fisierul de intrare")
    return
  
  # Extragem N, M și V din prima linie
  try:
    N, M, V = map(int, linii[0].split())
  except ValueError:
    # Scriem mesaj de date invalide în fișierul de ieșire
    with open('ambuscada.out', 'w') as f:
      f.write("Date invalide: Linia 1 nu contine suficiente valori")
    return
  
  # Verificăm dacă există suficiente atacuri în fișierul de intrare
  if len(linii) - 1 < M:
    # Scriem mesaj de date invalide în fișierul de ieșire
    with open('ambuscada.out', 'w') as f:
      f.write("Date invalide: Nu sunt suficiente atacuri in fisierul de intrare")
    return
  
  # Citim atacurile
  atacuri = [tuple(map(int, line.split())) for line in linii[1:M+1]]
  
  # Verificăm datele de intrare
  if not verificare_date_intrare(N, M, V, atacuri):
    # Scriem mesaj de date invalide în fișierul de ieșire
    with open('ambuscada.out', 'w') as f:
      f.write("Datele de intrare sunt invalide")
    return
  
  # Calculăm numărul de soldați rămași în viață
  soldati_ramas = soldati_ramasii(N, M, V, atacuri)
  
  # Scriem rezultatul în fișierul de ieșire
  with open('ambuscada.out', 'w') as f:
    f.write(str(soldati_ramas))

if __name__ == "__main__":
  main()