007 Datorii

[•filipb]

Uite functiile de update si query:

Cod:

int query(int x)
{
    int r = 0;
    for (; x; x -= x ^ (x-1) & x)
        r += A[x];
    return r;
} 

Cod:

void update(int x, int v)
{
      for (; x <= n; x += x^(x-1) & x)
          A[x] += v;
}

Si cand citesti operatiile din fisier, pur si simplu apelezi functiile. Iar ca sa determini suma pe secventa <i,j> faci query(j)-query(i-1).
Si nu mai postati surse      
Spatiu irosit de aiurea pe forum.

Si eventual sterge-l tu cu butonul edit!!!

Edited by svalentin: tagul e "code", nu "quote" pentru formatare corecta

[•devilkind]

Filip, cum explici faptul ca folosind functiile pe care u le-ai scris mai sus obtin TLE la toate testele?

[u-92]

in ce lucrezi ? daca in pascal nustiu ce sa zic, dar eu am trimis mai`nainte surse cu extensia .c si .cpp si intra in timp

[•devilkind]

c++, shi am trimis mai devreme o sursa folosind aceste 2 functii shi nu mi-a intrat in timp.

Dak vrei iti trimit un pm cu sursa sa vezi daca e bine ce am facut.

[Later edit] am luat 100 intre timp, eu citeam cu streamuri. mersi u-92. Pacat ca mi-am dat seama asha tarziu, mi-am batut capul o gramada incercand tot felul de optimizari, cand nu trebuia decat sa schimb functia de citire.  

[•devilkind]

tibilets vezi sa foloseshti fscanf si fprintf, dak foloseshti streamuri nu o sa iti intre in timp orice optimizari ai face u, asha am patit shi eu. Dak nici asha nu iti merge trimite-mi sursa pe privat, nu o mai posta pe forum ptr ca poate fi o gresheala minora pe care uni sa o vada shi sa dea copy paste.

[nivan]

 Fac cu arbori indexati binar si folosesc scanf() printf() cu freopen(). Am optimizat cat am putut... totusi scot doar 80 puncte  (TLE pe testul 4).   Singura optimizare pe care nu am facut-o e ca folosesc functii pentru Add, Sub si GetSum (adica sa introduc un element, sa scad valoarea unui element si sa gasesc suma pe intervalul <in,sf> )    . Folosesc functii si pentru a obtine cate zerouri are la sfarsit un numar in binar.
 Totusi nu cred ca influenteaza faza cu functiile.............

[u-92]

de ce nu afli numarul de zero-uri terminale in timp constant?

[nivan]

nu prea inteleg la ce te referi.... 

[u-92]

uita-te la postul de mai sus al lui filipb, la functiile alea.. "x+=x^(x-1)&x" sare direct la numarul care trebuie

[nivan]

ms... pe viitor voi citi si mai sus pe forum

[Last Edit] Si eu parcurgeam ca prostu' prin ele......

[•pocaitu]

 Iau WA pe toate testele cu toate ca mie imi merge bine .
 Am auzit ca daca vrei sa citesti cu scanf() un numar long int nu faci scanf("%ld",&x); ca in linux nu merge . E adevarat  ?

[u-92]

poti face un program la a+b sa testezi
legat de WA, ai generat teste aleator si programul tau da acelasi raspuns cu brute-force`ul?

[ditzone]

Tipul de date e long long.
Citirea si afisarea se aface cu %lld

[•pocaitu]

 Gata , am luat 100 
 

legat de WA, ai generat teste aleator si programul tau da acelasi raspuns cu brute-force`ul?

   Da, numai ca testele le faceam eu
  Ar trebui specificat de long long in restrictiile problemei

[•cos_min]

chiar nu inteleg de ce iau WA pe toate testele. Fac cu arbori de intervale, folosesc long long . Toate testele care le dau imi ies.   
poate sa ma ajute cineva?
[ii trimit sursa mea eventual ?]

[•cos_min]

  in sfarsit 100. multumesc celor care m-au ajutat. [greseala era ca declar prea mica dimensiunea arborelui  ]

[•gabitzish1]

iau 212ms si 216 ms  .. cred k renunt la ea

[•marcelcodrea]

Probabil ca ai timpi de 212 si 216 ms pt ca evaluatorul intrerupe rularea programului dupa expirarea timpului limita , deci nu e relevant ! 

[•cos_min]

Daca faci cu arbori de intervale renunta incearca AIB intra lejer in timp 

[•gabitzish1]

sunt doar clasa a 10'a.. si inca nu am invatzat chestii d'astea ca si "arbori indexati binari".. o alta solutie mai accesibila exista?

[•devilkind]

nu prea, dar daca ai sa citesti un articol despre arbori indexati binari (google it) cu siguranta vei intelege.

[•sima_cotizo]

Nu e greu chiar daca esti a zecea... Si daca vrei sa treci peste exprimarea "pretentioasa" de aib, incearca sa vezi de fapt ce ar trebui sa aplici aici... si ai sa vezi ca nu e mare lucru...
Poate nu m-am exprimat eu cum trebuie, dar ideea ar fi sa nu te sperii de un nume de algoritm care pare mai ciudat...

[•vanila0406]

e un articol in ginfo foarte bun despre arborii indexati binar...asta e linku: http://www.ginfo.ro/revista/13_1/focus.pdf sper sa fie de folos 

[•Darth_Niculus]

 Deci problema asta ma scoate din sarite de ceva timp.....   cand o rezolv cu AIB iau 100 pct.......... cand incerc cu arbori de intervale iau 0 pct..... cu TLE pe toate testele..... pai ambele surse au aceeasi complexitate adica O(MlogN).
 Chiar ar trebui sa fie un pic mai rapid cu arbori de intervale.... pt ca nu tre sa interoghez de 2 ori arborele ca sa aflu care e suma in Query.....   

[•astronomy]

Din contra, un aib merge mai bine decat un arbore de intervale [dar la problema asta merge de 100 si cu arbori de intervale]