infoarena

Aici puteţi discuta despre problema Zoo (http://infoarena.ro/problema/zoo).

Care este complexitatea oficiala ????

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.

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

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?

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

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

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.

Multumesc. :)

mie mi-a intrat in timp si fara acel rafinament

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 :-?.

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.

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.

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!  :peacefingers:

PS Parsez citirea

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;

}

}

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 :winner3: