Fișierul intrare/ieșire paznici.in, paznici.out Sursă Olimpiada pe scoala 2015
Autor Victor Manz Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.3 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Paznici (clasele 11-12)

Pentru a proteja cea mai bună școală din țară de atacurile teroriste, guvernul a hotărât să încheie un contract cu o firmă de protecție și pază. Fiecare firmă are asociat un cod numeric și poate asigura paza numai în anumite intervale de timp (fiecare dintre angajații săi poate lucra în anumite intervale de timp). Guvernul dorește asigurarea pazei între momentele de timp A și B. În acest scop va alege acea firmă pentru care perioada de timp din intervalul [A,B] neacoperită cu agenți de pază este cea mai scurtă. Dacă vor exista mai multe firme aflate la egalitate conform acestui criteriu, atunci va fi aleasă cea având codul numeric mai mic.

Date de intrare

Fișierul de intrare paznici.in conține pe prima linie numerele A și B reprezentând perioada în care trebuie asigurată paza. Pe cea de-a doa linie se va afla numărul total de paznici, N. Pe următoarele N linii se vor afla câte trei numere X, Y și C reprezentând intervalul de timp și codul firmei la care este angajat fiecare paznic în parte.

Date de ieșire

În fișierul de ieșire paznici.out se va scrie un singur număr reprezentând codul firmei alese.

Restricții

  • 0 ≤ A < B ≤ 1 000 000 000
  • 1 ≤ N ≤ 100 000
  • A ≤ X < Y ≤ B pentru fiecare paznic în parte
  • 1 ≤ C ≤ 1000 pentru fiecare paznic în parte

Exemplu

paznici.in paznici.out
1 10
3
1 4 1
3 10 2
8 10 1
2

Explicație

Firma 2 va lăsa școala nepăzită între 1 și 3 ( 2 unități de timp ) în timp ce firma 1 nu va păzi școala între 4 și 8 ( 4 unități de timp)

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii