637 Stergeri

[•filipb]

Aici puteţi discuta despre problema Stergeri.

[•Robytzza]

am citit articolul in care este rezolvata problema si nu o inteleg ma ajuta si pe mine sa inteleg cum este solutia  multumesc anticipat

[•stef2n]

Incearca sa pui problema invers. In loc sa te intrebi ce element e pe pozitia K dupa M stergeri, intreaba-te pe ce pozitie va ajunge al K-lea element dupa M inserari. Executi pasii pe dos.

[•drag0s93]

salut am si yo o intrebare.....am citit si yo comentariul lui stef si vreau sa intreb ca dak o caut pe ce poz ajunge al k-lea dupa m inserari .....dak acel nr trb sa fie sters  ? 

[•Mishu91]

Pai ideea este sa iei intervalele date in ordine inversa si sa verifici daca pozitia actuala se va schimba dupa inserarea intervalului curent (adica sa verifici daca pozitia actuala e mai mare decat limita inferioara a intervalului ce trebuie inserat). Daca da, atunci pozitia actuala se va deplasa la dreapta, daca nu, nu

[•Bogdan_tmm]

Cum as putea sa dau un seek pana la sfarsitul fisierului (dupa ce citesc prima linie) si sa citesc treptat cate o linie de jos in sus?

[•toni2007]

Nu cred ca poti. Poti tine insa o stiva cu numerele, si accesezi in ordine inversa.

Spor

[•Bogdan_tmm]

Facui si o varianta recursiva dar tot am un timp cam marisor .

[•toni2007]

Stiva e iterativa, deci e mai rapida decat varianta recursiva. Intotdeauna variantele iterative sunt mai rapide decat variantele recursive cu aceeasi complexitate

[•Bogdan_tmm]

Oricum am luat 100 cu ambele.Eu vroiam un timp mai bun dar...

[•shnako]

Pe sursa asta primesc Killed by Signal 11 pe 7 teste  Am scos vectoru si tot aia imi da. 8 longuri ma gandesc ca imi intra in 16MB cat e limita de memorie. Pe site scrie ca Killed by Signal 11 ii legat in 99% din cazuri de alocarea memoriei... Mi se pare mie sau am nimerit in restu ala de 1% ? 

Cod:

#include <stdio.h>  
long i, j, t, x, y, n, m, k;    
bool v[200001];    
int main()    
{    
freopen("stergeri.in", "r", stdin);    
freopen("stergeri.out", "w", stdout);    
scanf("%ld%ld%ld", &n, &m, &k);    
for (i=1;i<=n;i++)    
    v[i]=1;  
for (i=1;i<=m;i++)    
    {    
   t=0;    
   scanf("%ld%ld", &x, &y);  
   for (j=1;t<x;j++)    
    if (v[j]==1)    
        t++;    
   for (j=t;t<=y;j++)    
    if (v[j]==1)  
        {    
         t++;    
         v[j]=0;  
         }    
   }    
t=0;  
for (i=1;t<k;i++)    
    if (v[i]==1)    
    t++;  
printf("%ld", i-1);  
fcloseall();    
return 0;    
}  

[•c_e_manu]

cred ca poti sa iei KBS11 si daca depasesti limitele unui vector... parca ai mai avut eroarea asta la inca o problema

[•VisuianMihai]

Pe sursa asta primesc Killed by Signal 11 pe 7 teste  Am scos vectoru si tot aia imi da. 8 longuri ma gandesc ca imi intra in 16MB cat e limita de memorie. Pe site scrie ca Killed by Signal 11 ii legat in 99% din cazuri de alocarea memoriei... Mi se pare mie sau am nimerit in restu ala de 1% ? 

Nu stiu dc dar bool-ul si mie imi mai facea figuri la unele proleme. Declara vectorul normal int.