131 Geamuri

[•domino]

Aici puteţi discuta despre problema Geamuri.

[andreit1]

Cam in ce complexitate ar trebui sa rezolv problema, tinand cont ca citirea si afisarea unui 0 pentru fiecare intrebare dureaza 0.12 secunde pe ultimul test( stiu ca timpii din monitor sunt orientativi, dar probabil se apropie de realitate)?
Sursa folosita:

Cod:

var fi,fo:text;
    i,x1,y1,x2,y2,c,n,x:word;
begin
 assign(fi,'geamuri.in'); reset(fi);
 assign(fo,'geamuri.out'); rewrite(fo);
 readln(fi,c); readln(fi,n);
 for i:=1 to n do readln(fi,x1,y1,x2,y2);
 readln(fi,n);
 for i:=1 to n do
  begin readln(fi,x); writeln(fo,0); end;
 close(fo);
end.

[•domino]

Am schimbat limita la 0.2s

[•filipb]

O(N log^2 C + M) ajunge?    :cry:

[•greco]

Nu stiu, dar cred ca a fost data la C^2 + N + M.

[•filipb]

Da, asa e  

[•Cosmin]

Fiecare geam ce contine acel punct se va sparge

In problema nu se intelege ca tu vrei un punct inclus in ki dreptunghiuri, daca glontul i sparge geamuri atunci glontul i + 1 va sparge din geamurile ramase ... nu tot din geamurile initiale, enuntul induce in eroare pe cei ce vreau sa rezolve problema !!!!!!!!!

[•y2k]

Ce e gresit in codul asta? (poate sunt eu prost si nu-mi dau seama, dar mi se pare corect). La codu' asta iau 0 punct.
   

Cod:

#include<fstream>
#define IN_FILE  "geamuri.in"
#define OUT_FILE "geamuri.out"
std::ifstream IN;
std::ofstream OUT;
long n,m,c,a[1025][1025],b[50001];
void adaugaGeam(int x1, int y1, int x2, int y2)
{
 int i,j;
 for(i=y1; i<=y2; ++i)
    for(j=x1; j<=x2; ++j)
       {
        --b[a[i][j]];
        ++a[i][j];
        ++b[a[i][j]];
        }
 }
void citire()
{
 IN>>c;
 IN>>n;
 int i,x1,y1,x2,y2;
 for(i=1; i<=n; ++i)
    {
     IN>>x1;
     IN>>y1;
     IN>>x2;
     IN>>y2;
     adaugaGeam(x1,y1,x2,y2);
     }
 IN>>m;
 for(i=1; i<=m; i++)
     {
      IN>>x1;
      OUT<<b[x1]<<"\n";
      }
 }
int main()
{
 IN.open(IN_FILE);
 OUT.open(OUT_FILE);
  citire();
 IN.close();
 OUT.close();
 return 0;
 }

  Sa-mi spuneti daca e gresti, nu vreau sa-mi spuneti ce am gresit, o sa ma gandesc eu la asta

[•danielp]

Pai daca iei 0 puncte nu e clar ca e gresit? Poate doresti sa iti spunem ce ai gresit:)

[•y2k]

ai dreptate... poate imi spui

[•greco]

Asteapta sa-ti depaneze altii codul, si o sa ajungi departe.

[ditzone]

In primul rand sunt convins ca iei destule TLE si ar trebui sa te gandesti la o alta complexitate si in al doilea rand.. esti sigur ca raspunzi corect la intrebarile pentru K=0 ?

[•devilkind]

la primu query in exemplu zice ca ar fi un singur punct si anume: (5 4). Mie mi se pare ca si (5 3) e corect deci ar fi 2 puncte. Ce nu am inteles bine??

[•DITzoneC]

Pai daca tragi din (5,3) nu atingi ultimul geam, atingi doar primele 2.

[•Andrei1998]

Sunt si eu curios de ceva legat de problema:
Daca Geminski are doua variante de a trage primul glont pe care o va alege? Intreb asta deoarece Cosmin Negrusesti a spus ca dupa ce se trage primul glont, geamurile sparte de el dispar si astfel raspunsurile pentru urmatoarele gloante pot diferi in functie de ce alegere face Geminski pentru glontul cu 2 variante.

Ex. Se poate sa dispara puncte unde se sparg 4 geamuri daca alegem o varianta de la glontul 1 sau sa nu dispara daca o alegem pe cealalta.

Multumesc anticipat.

Mentionez ca am gasit rezolvarea cu Smenul lui Mars deja.

L.E.: Rezolvat!

[•Mihai22e]

Cred ca ar trebui marita un pic limita  . Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).

[•Magnvs]

Cred ca ar trebui marita un pic limita  . Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).

merge fara parsare. tu aloci prea multa memorie si de-aia iesi din timp cred.

vezi ca poti sa tii S in A, avand in vedere ca nu mai folosesti A odata ce iti creezi S.

[•Mihai22e]

Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data 

[•Magnvs]

Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data 

tu parcurgi coloana cu coloana.
trebuie sa parcurgi linie cu linie ca sa nu spargi cache-ul.

[•Mihai22e]

Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?

[•Magnvs]

Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?

matricile in c/c++ sunt retinute linie cu linie, iar cand pargurgi linie cu linie tu treci la elementul cu 1 poz in dreapta, dar coloana cu coloana sari vreo 1000 de elemente in cazul de fata.

cacheul e niste memorie care poate fi accesata rapid, iar tu cand accesezi un element al unui vector procesorul presupune ca o sa ai nevoie si de urmatoarele elemente si ti le baga in cache.

[•Mihai22e]

Nu stiam. Thanks!