010 Distincte2

[•dushmi]

Aici puteţi discuta despre problema Distincte2.

[•andreeainfo_d]

Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste.
Eu la sursa mea am economisit cata memorie am putut dar tot nu merge
Sursa mea este:

Cod:

using namespace std;
#include<stdio.h>
int i,n,mm,m,v[100001],a,q,l,x,y;
int main()
{
	freopen("distincte2.in","r",stdin);
	freopen("distincte2.out","w",stdout);
	scanf("%d%d",&n,&mm);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		v[a]=1;
		if(m<a)m=a;
	}
	for(l=1;l<=mm;l++)
	{
		q=0;
		scanf("%d%d",&x,&y);
		for(i=1;i<=m;i++)
		{
			if(v[i]>0)
			{
				if(i>=x&&i<=y)q++;
			}
		}
		printf("%d\n",q);
	}
	return 0;
}

Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie!
Multumesc!

Editat de admin: De acum incolo, posteaza in topicul problemei (http://infoarena.ro/forum/index.php?topic=7803.0)

[•blasterz]

Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste.
Eu la sursa mea am economisit cata memorie am putut dar tot nu merge
Sursa mea este:

using namespace std;
#include<stdio.h>
int i,n,mm,m,v[100001],a,q,l,x,y;
int main()
{
   freopen("distincte2.in","r",stdin);
   freopen("distincte2.out","w",stdout);
   scanf("%d%d",&n,&mm);
   for(i=1;i<=n;i++)
   {
      scanf("%d",&a);
      v[a]=1;
      if(m<a)m=a;
   }
   for(l=1;l<=mm;l++)
   {
      q=0;
      scanf("%d%d",&x,&y);
      for(i=1;i<=m;i++)
      {
         if(v[ i ]>0)
         {
            if(i>=x&&i<=y)q++;
         }
      }
      printf("%d\n",q);
   }
   return 0;
}


Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie!
Multumesc!

Tu folosesti ~400 KB memorie iar limita e de 16MB, deci iti intra sigur in memorie.

Din cate vad, tu la citire faci v[a] = 1; unde 1 <= a <= 1.000.000 iar tu ai declarat vectorul de 100.000
In plus, daca vectorul v va tine doar valori 1 si 0, nu are sens sa-l declari int, pune-l char.

La alt 2lea for nu trebuia sa mergi de la x la y ?

In plus, nu te astepta la punctaj maxim, asta e o solutie triviala.

[•NicuCJ]

Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste.
Eu la sursa mea am economisit cata memorie am putut dar tot nu merge
Sursa mea este:

Cod:

using namespace std;
#include<stdio.h>
int i,n,mm,m,v[100001],a,q,l,x,y;
int main()
{
	freopen("distincte2.in","r",stdin);
	freopen("distincte2.out","w",stdout);
	scanf("%d%d",&n,&mm);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		v[a]=1;
		if(m<a)m=a;
	}
	for(l=1;l<=mm;l++)
	{
		q=0;
		scanf("%d%d",&x,&y);
		for(i=1;i<=m;i++)
		{
			if(v[i]>0)
			{
				if(i>=x&&i<=y)q++;
			}
		}
		printf("%d\n",q);
	}
	return 0;
}

Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie!
Multumesc!

Editat de admin: De acum incolo, posteaza in topicul problemei (http://infoarena.ro/forum/index.php?topic=7803.0)

Nu e bine cum faci, complexitatea ta finala e N*M (daca toate numerele pe care le citesti la inceput sunt distincte), ceea ce e imposibil in 0.25 sec.
Daca vrei, iti dau un indiciu, ar trebui sa scoti M*logN sau ceva de genul ca sa-ti intre.
P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes

[•blasterz]

P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes

Unde vezi tu 1.000.000.000 in enuntul problemei? eu vad 1.000.000

[•visanr]

Poti sa faci in O(N) fara set sau map.

[•NicuCJ]

P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes

Unde vezi tu 1.000.000.000 in enuntul problemei? eu vad 1.000.000

Oops, imi cer scuze pentru inducerea in eroare. Nu stiu ce am avut la momentul cand am citit problema de am citit asa. In cazul asta merge f. bine si cu un bool de 1 milion. Scuze inca odata :-".

[•nicolaetitus12]

La cineva ii intra in timp cu fstream? mie doar cu stdio imi intra in timp.