Fişierul intrare/ieşire:secv8.in, secv8.outSursăLot Bistrita 2009, Baraj 2
AutorMarius StroeAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test2.5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Secv8

Se consideră un şir S, iniţial vid. Asupra acestuia se efectuează patru operaţii:

  1. insert(k, e): inserează în S elementul e pe poziţia k;
  2. access(k): întoarce elementul de pe poziţia k;
  3. reverse(i, j): schimbă ordinea elementelor din subşirul S[i..j];
  4. delete(i, j): şterge subşirul S[i..j].

Cerinţă

Se cere să se răspundă la toate operaţiile de tipul 2 şi să se afişeze elementele şirului S după efectuarea tuturor operaţiilor.

Date de intrare

Pe prima linie a fişierului de intrare secv8.in se vor găsi două numere naturale, primul reprezentând numărul operaţiilor din fişier, iar al doilea va fi 1 dacă există operaţia reverse şi 0 dacă nu există. Următoarele linii vor fi de patru tipuri, corespunzătoare fiecărei operaţii:

  1. I k e: insert(k, e), unde e este un număr natural cuprins în intervalul [0, 109] iar k un număr natural cuprins în intervalul [1, n+1].
  2. A k: acces(k), unde 1 ≤ k ≤ n.
  3. R i j: reverse(i, j), unde 1 ≤ i ≤ j ≤ n.
  4. D i j: delete(i, j), unde 1 ≤ i ≤ j ≤ n.

Cu n am notat lungimea şirului.

Date de ieşire

În fişierul de ieşire secv8.out se vor tipări pe câte un rând răspunsurile operaţiilor de tipul 2 în ordinea în care apar în fişierul de intrare. Pe ultima linie se va tipări secvenţa S după efectuarea tuturor operaţiilor.

Restricţii şi precizări

  • Numărul operaţiilor insert nu va depăşi 250 000.
  • Numărul total al operaţiilor nu va depăşi 750 000.
  • Operaţia insert(k, e) va transforma şirul S: s1s2..sk..sn în S’: s1s2..esk..sn.
  • Operaţia reverse(i, j) va transforma şirul S: s1..si-1sisi+1..sj-1sjsj+1..sn în S’: s1..si-1sjsj-1..si+1sisj+1..sn.
  • Operaţia delete(i, j) va transforma şirul S: s1..si-1sisi+1..sj-1sjsj+1..sn în S’: s1..si-1sj+1..sn.
  • Se garantează că operaţiile 2, 3 şi 4 nu se vor efectua asupra unei secvenţe vide.
  • Pentru 15% din teste numărul operaţiilor insert nu va depăşi 35 000 iar numărul total al operaţiilor 100 000. Pentru aceste teste va exista operaţia reverse.
  • Pentru încă 25% din teste operaţia reverse nu se va regăsi.

Exemplu

secv8.insecv8.out
13 1
I 1 1
I 2 2
I 3 3
R 2 3
I 4 4
I 3 5
A 4
R 1 3
D 2 3
A 3
I 2 1
R 1 3
D 3 3
2
4
2 1 4

Explicaţie

Şirul S devine succesiv: 1, 1 2, 1 2 3, 1 3 2, 1 3 2 4, 1 3 5 2 4, 5 3 1 2 4, 5 2 4, 5 1 2 4, 2 1 5 4, 2 1 4. Numerele îngroşate sunt răspunsurile operaţiilor de tipul 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content