Lista de probleme 3

Tsubasa-chan adoră dulciurile! De curând a apărut un nou tip de desert. Astfel decide să înfăptuiască o nouă fabrică care să producă acest produs delicios. Fabrica conține un container imens pătratic, plin de aluat, de 106 x 106 unități. Fiecare punct din container are drept coordonate o pereche de numere reale (x, y), unde 0 ≤ x, y ≤ 106, iar fiecare punct are o dulceață. Dându-se toate operațiile întreprinse în producerea desertului, să se găsească dulcețurile totale ce sunt găsite la toate operațiile de degustare.

După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive. Fiind date Q seturi de valori zi, zf, cl, cr, el doreşte să afle ce sumă a investit în perioada cuprinsă între zilele zi și zf (inclusiv acestea), la companiile cu numere de ordine cuprinse între cl și cr (inclusiv acestea).

Ariciul Gălușcă este un arici obișnuit pe timp de zi. Noaptea, însă, el este de fapt eroul misterios al orașului Hedgytown – un oraș mai special, deoarece are clădiri atât deasupra solului, cât și sub pamânt, unde gravitația este inversată. Orașul poate fi văzut ca o dreaptă (ce reprezintă solul), cu un șir de clădiri dreptunghiulare lipite deasupra solului, și un șir de clădiri dreptunghiulare lipite dedesubtul solului. Sunt N clădiri peste pământ și M sub pământ. Cele două șiruri încep și se termină la aceleași poziții. Fiecare clădire este caracterizată de trei valori: L, H și E. L reprezintă lățimea clădirii, H reprezintă înălțimea clădirii și E reprezintă efortul necesar pentru a folosi liftul din acea clădire. Se cere să se afle numărul minim de unități de efort pe care trebuie să le depună ariciul Gălușcă pentru a ajunge la destinația sa.