Fişierul intrare/ieşire:stergeri.in, stergeri.outSursăpreONI 2008 Runda 3
AutorDin FolclorAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stergeri

Magicianul Dino a scris pe o foaie in ordine numerele naturale de la 1 la N (adica 1 2 3 .. N). Frasinel a ales doi indici x si y (x ≤ y) si Dino a sters toate elementele aflate intre pozitiile x si y. Apoi Dino ii spune lui Frasinel sa aleaga alti doi inidici si va realiza acelasi lucru pentru elementele ramase scrise pe foaie. Dupa M operatii de acest tip, Frasinel ar vrea sa stie ce element se afla pe pozitia K pe foaie.

Date de intrare

Fisierul de intrare stergeri.in contine pe prima linie numerele N M K avand semnificatia din enunt. Urmeaza M linii ce contin doua numere intregi x y reprezentand indicii din operatia efectuata de Frasinel.

Date de iesire

In fisierul de iesire stergeri.out se afla pe prima linie un numar SOL, reprezentand numarul care se afla pe foaie la pozitia K dupa efectuarea tuturor operatiilor.

Restrictii

  • 1 ≤ N ≤ 2 000 000 000
  • 1 ≤ M ≤ 100 000
  • K va fi cel mult numarul de elemente ramase la sfarsit pe foaie

Exemplu

stergeri.instergeri.out
12 2 3
4 7
2 6
12

Explicatie

Dupa prima operatie foaia arata asa: 1 2 3 8 9 10 11 12. Dupa cea de-a doua operatie: 1 11 12. Deci pe pozitia 3 se afla numarul 12.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content