Balloons – Épreuve régionale 2014

Énoncé¶

Joseph Marchand vient de tomber sur de veilles photos d'anniversaires, remplies de ballons de baudruches. Nostalgique, il a décidé de se lancer dans la vente de ces ballons qui lui rappellent son enfance. Après s'être renseigné, il a appris qu'il existait de nombreuses utilisations de ces ballons : pour un anniversaire, pour en faire des sculptures, pour faire de la musique. Il paraît même qu'à la finale d'un certain concours d'informatique il est coutume de les remplir d'eau et de les lancer sur les organisateurs.

Chaque ballon de baudruche est caractérisé par son prix ainsi que son élasticité, laquelle est déterminante pour l'usage qu'on souhaite en faire. Chacun des clients de Joseph vient acheter des ballons dont l'élasticité est comprise dans un intervalle bien précis, correspondant à une utilisation bien précise. S'il reste des ballons dont l'élasticité est comprise dans cet intervalle, Joseph vend à son client le paquet de tels ballons le moins cher qu'il reste en stock (tous les ballons ont des prix différents). Dans le cas contraire, le client repart chez lui les mains vides.

On vous décrit les stocks de Joseph par les prix et élasticités des paquets de ballons qu'il possède. On vous donne aussi les intervalles d'élasticité demandés par les clients, dans l'ordre où ils se présentent au magasin. Vous devez calculer le chiffre d'affaires de M. Marchand pour ces ventes.

Entrée¶

• Sur la première ligne : N, le nombre de paquets de ballons que Joseph a en stock et R, le nombre de clients
• Sur les N lignes suivantes : l'élasticité e_i et le prix p_i du i-ème paquet de ballons
• Sur les R dernières lignes : a_j <= bles bornes (incluses) de l'intervalle d'élasticité demandé par le j-ème client

Sortie¶

En sortie, vous devez afficher le chiffre d'affaire de M. Marchand après que tous les clients se sont présentés au magasin.

Contraintes¶

• 1 <= N <= 300 000
• 1 <= R < 200 000
• 0 <= e_i <= 1 000 000
• 0 <= p_i <= 1 000 000
• 0 <= a_j <= b_j <= 1 000 000
• Attention : pour valider cet exercice il faut un algorithme efficace, et pas seulement un algorithme correct.