Fișierul intrare/ieșire	hibrid.in, hibrid.out	Sursă	OJI 2023 Clasa a 8-a
Autor	Andrei Onuț	Adăugată de	David Demetriad • demetriad-dagpag
Timp de execuție pe test	0.25 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Hibrid (clasa a 8-a)

O mașină hibrid se deplasează pe o șosea rectilinie folosind, alternativ, fie motorul termic (pe benzină), fie motorul electric. Axa numerelor întregi poate fi folosită pentru a descrie coordonatele de pe șosea. Deplasarea mașinii folosind motorul electric se efectuează fără taxă, dar unele porțiuni din șosea necesită folosirea motorului termic, ceea ce impune plata anumitor taxe. Se cunoaște lista celor P porțiuni taxabile de șosea, numerotate de la 1 la P, oricare două dintre ele fiind disjuncte. Fiecare porțiune este descrisă de trei numere întregi: st_i, dr_i și c_i (1 ≤ i ≤ P), cu semnificația că pe porțiunea de șosea situată între coordonatele st_i și dr_i (inclusiv la capetele st_i și dr_i) se va folosi motorul termic și se va achita taxa în valoare de c_i lei. Această taxă se va plăti la fiecare traversare a porțiunii, indiferent de sensul deplasării.

Traseul pe care mașina hibrid îl are de străbătut conține N borne amplasate pe șosea, numerotate de la 1 la N, în ordinea în care acestea trebuie vizitate. Pentru fiecare dintre cele N borne se cunoaște coordonata poziției sale pe șosea: x₁, x₂, x₃, ..., x_N. Deplasarea între două borne consecutive de pe traseu, adică între borna i și borna [i+1] (pentru fiecare i: 1 ≤ i < N), se face pe drumul cel mai scurt, respectiv pe segmentul de dreaptă ce unește punctele cu coordonatele x_i și x_i+1 de pe șosea. Mașina hibrid va începe traseul din dreptul bornei cu numărul de ordine 1, adică de la coordonata x₁ de pe șosea. De asemenea, se știe că nicio bornă de pe traseu nu se află în interiorul sau la capetele porțiunilor taxabile, unde se folosește deplasarea cu motorul termic.

Cerințe

Să se determine:

1. numărul de ordine al porțiunii taxabile peste care se va trece de cele mai multe ori în călătorie (folosind motorul termic). Dacă există mai multe astfel de porțiuni, se va alege cea cu indicele minim, în funcție de ordinea dată în fișierul de intrare. De asemenea, în caz că nu se va trece peste nicio porțiune taxabilă, acest număr va fi egal cu -1.
2. suma totală, exprimată în lei, care trebuie plătită pentru a parcurge traseul stabilit. În caz că nu se va trece peste nicio porțiune taxabilă, atunci această sumă va fi egală cu 0.

Date de intrare

Pe prima linie a fișierului de intrare hibrid.in se află, separate între ele prin câte un spațiu, trei numere naturale, C, P și N, cu semnificațiile din enunț. C poate avea fie valoarea 1, fie valoarea 2, în funcție de cerința care trebuie rezolvată. Pe următoarele P linii se află, separate între ele prin câte un spațiu, câte trei numere întregi: st_i, dr_i și c_i, cu semnificația de mai sus. Pe următoarea linie se află N numere întregi, separate între ele prin câte un spațiu, reprezentând, în ordine, coordonatele bornelor ce trebuie vizitate: x₁, x₂, x₃, ..., x_N.

Date de ieșire

Fișierul de ieșire hibrid.out va conține, pe prima linie, un singur număr întreg, în funcție de cerința care trebuie rezolvată. Dacă C = 1, atunci se va rezolva cerința 1, altfel, se va rezolva cerința 2.

Restricții și precizări

• 2 ≤ P ≤ 100 000 și 2 ≤ N ≤ 200 000;
• -300.000 ≤ st_i < dr_i ≤ 300 000 și 1 ≤ c_i ≤ 100 000, pentru fiecare i: 1 ≤ i ≤ P;
• -1.000.000 ≤ x_i ≤ 1 000 000, pentru fiecare i: 1 ≤ i ≤ N;
• Întrucât au dimensiuni neglijabile, pot exista și două sau mai multe borne situate la aceeași coordonată pe șosea;
• Pe durata întregului traseu, motorul termic (pe benzină) este utilizat doar pentru parcurgerea porțiunilor taxabile peste care mașina hibrid trebuie să treacă. În rest, se folosește doar motorul electric, pentru a reduce poluarea;

Exemple