Fişierul intrare/ieşire:ambuscada2.in, ambuscada2.outSursăRAUCoder 2020
AutorAdam Altar-Samuel, Daniela Alexandra CrisanAdăugată deRAUCoderDaniela Alexandra Crisan RAUCoder
Timp execuţie pe test0.025 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ambuscada2

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 ambuscada2.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 ambuscada2.out va conţine un singur număr natural reprezentând numărul de soldaţi rămaşi în viaţă.

Restricţii

  • 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

Exemplu

ambuscada2.inambuscada2.out
6 4 10
2 5 2
1 3 7
2 6 3
3 5 6
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?