119 Zoo

[•bogdan2412]

Aici puteţi discuta despre problema Zoo.

[•dobre]

Care este complexitatea oficiala ?

[•filipb]

Pai eu am facut un algoritm care imi rezolva fiecare query in O(log^2 N), deci complexitatea finala O(M log^2 N) ( ma rog, se mai adauga si un NlogN de la sortare ) si a luat 100 pct. Daca nu se incadreaza asta in timp, poti rezolva un query si in O(log N), aplicand un rafinament...

                                                              Filip b.

[•Dorin]

Nu stiti de ce mi da    Killed by signal 11(SIGSEGV) pe 3 teste ?? am aceeasi complexitate ca si Filip B. si memorie nlogn ?? ... arborele il construiesc recursiv

[•Florian]

Nu prea inteleg de ce imi trebuie sortare....iau doar 30 pcts...si pe restul TLE..insa nu stiu la ce ma ajuta sortarea...[totusi sunt constient k trebuie k sa mi se incadreze in timp]..ma poate ajuta cineva?

[•devilkind]

pai iti trebuie un arbore de intervale in primul rand, si tre sa sortezi elementele din acele intervale.

[•Florian]

Ee..ink nu am invatat...DEci sa inteleg k trebuie sa ma multumesc cu 30,nu?..asta e..multumesc de ajutor

[•peanutz]

Si cum se poate face query in logn? In logn*logn mi-am dat si eu seama.

[•Marius]

Si cum se poate face query in logn? In logn*logn mi-am dat si eu seama.

Cu rafinamentului lui Willard-Lueker. Il gasesti in documentul Arbori de Intervale al doamnei Lica predat la lotul din 2006.

[•peanutz]

Multumesc.

[•devilkind]

mie mi-a intrat in timp si fara acel rafinament

[•APOCALYPTO]

Imi poate explica si mie cineva de ce daca pun <= in loc de < la functia cmp din sursa mea de 100 de puncte iau 80?
Teoretic interschimba 2 puncte cu acelasi x si nu vad care ar fi problema .

[•toni2007]

Functia ta trebuie sa returneze True in caz ca primul element e mai mic decat celalalt. Daca ai 2 elemente egale si sunt comparate de 2 ori, iti poate da ca a < b si b < a, care o fi stricand vreun assert din sort-ul din STL, ceea ce duce la killed by signal 6.

[•Bit_Master]

Imi poate explica si mie cineva de ce daca pun <= in loc de < la functia cmp din sursa mea de 100 de puncte iau 80?
Teoretic interschimba 2 puncte cu acelasi x si nu vad care ar fi problema .

Poate le interschimba intre ele de mai multe ori pt ca oricum le-ar pune tot nu e bine. Pana la urma ele raman intr-o pozitie din cauza algoritmului care nu verifica in urma lui (ca altfel cred ca ar fi ciclat la infinit). Oricum, pierzi timp asa.
Eu asa cred.

[•repp4radu]

Cred ca ar trebui marita limita de timp. Iau 90 de puncte cu TLE avand complexitatea O(M * (log M + log N)).
Am incercat, de curiozitate sa trimit o sursa care acum ceva vreme lua 100, intrand lejer in timp si acum ia doar 80.

Mersi anticipat! 

PS Parsez citirea

[•catazep]

nu va suparati am si eu o intrebare pt cei mai experimentati
nu am cum sa ma incadrez in timp cu cv asemanator nu?

#include<fstream>
using namespace std;
struct reper
{int x,y;
};
reper v[16000];
reper a,b;
long unsigned N,M,i,j;
unsigned t;
int main()
{
ifstream f("zoo.in");
ofstream g("zoo.out");

f>>N;
for(i=1;i<=N;i++)
   f>>v.x>>v.y;
f>>M;
for(j=1;j<=M;j++)
{t=0;
f>>a.x>>a.y>>b.x>>b.y;
for(i=1;i<=N;i++)
   if(v.x>=a.x && v.y>=a.y && v.x<=b.x && v.y<=b.y)
      t++;
   g<<t<<endl;

}

}

[•catazep]

daca ar conta si spatiul utilizat as fi cel mai boss:)) toti au de la 2.00kb in sus si eu 0.4:)) si totus  functioneaza algoritmul meu doar ca nu e prea eficient:D