Fişierul intrare/ieşire:paint1.in, paint1.outSursăLot I Juniori 2015
AutorConstantin GalatanAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.3 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Paint1 (Lot Juniori)

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment îşi câştigă existenţa ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri şi înălţimea un metru. Pentru aceasta are la dispoziţie m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porţiune compactă de înălţime un metru şi de lungime li metri, începând de la distanţa di metri faţă de capătul din stânga al zidului. Roberto ştie din experienţă că fiecare porţiune de zid trebuie acoperită cu cel puţin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistenţa dorită. Din nefericire, firea lui de artist nu i-a permis să-şi poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porţiuni pe care le-a acoperit de mai mult de k ori şi alte porţiuni pe care le-a acoperit de mai puţin de k ori.

Pentru a recupera în proprii săi ochi dar mai ales în ochii şefului de echipă, el trebuie să afle mai întâi suprafaţa totală a tuturor porţiunilor de zid care mai trebuie zugrăvite.

Cerinţă

Cunoscând lungimea zidului n, numărul de zile m şi porţiunile compacte pe care le zugrăveşte în fiecare zi, determinaţi suprafaţa totală a zidului care mai trebuie zugrăvită.

Date de intrare

Fişierul de intrare paint1.in conţine pe prima linie trei numerele naturale n, k şi m separate printr-un spaţiu, unde n este lungimea zidului, k este numărul minim de straturi de vopsea pentru a se obţine consistenţa dorită, iar m este numărul de zile în care Roberto pictează.

Pe următoarele m linii se află câte două valori naturale separate prin câte un spaţiu. Numerele di şi li de pe linia i+1 reprezintă distanţa faţă de capătul din stânga al zidului de la care începe să zugrăvească în ziua i, respectiv lungimea în metri a porţiunii de zid zugrăvite în ziua i.

Date de ieşire

Fişierul de ieşire paint1.out conţine pe prima linie un număr natural S care reprezintă suprafaţa totală a zidului care nu a fost acoperită cu cel puţin k straturi de vopsea.

Restricţii

  • 1 ≤ n, m ≤ 250 000
  • 1 ≤ k ≤ min(250 000, m)
  • 0 ≤ di < li < n

Exemplu

paint1.inpaint1.out
5 2 3
0 2
1 3
2 3
2

Explicaţie

n = 5, k = 2, m = 3.
În prima zi Roberto vopseşte 2 m din zid între poziţiile 0 şi 2. În a doua zi Roberto vopseşte 3 m din zid între poziţiile 1 şi 4. În a treia zi Roberto vopseşte 3 m din zid între poziţiile 2 şi 5. Deci, începând cu capătul din stânga al zidului, se va găsi o porţiune de zid de lungime 1, acoperită cu un singur strat şi începând de la distanţa 4 faţă de capăt, se va găsi o altă porţiune de zid de lungime 1, acoperită cu un singur strat

Trebuie sa te autentifici pentru a trimite solutii. Click aici