Multumesc mult!
Am luat 100!

P.S. De acum inainte nu-am sa mai folosesc qsort-ul.

Salut!
Am incercat rezolvarea problemei ca in solutie(folosind un arbore de intervale) si iau 90pct(TLE pe testul 9),dar nu imi dau seama ce-as mai putea optimiza.
As vrea sa stiu daca normalizarea se mai poate imbunatati:

Cod:

          int arb[264010],n,v[100000]....;
          struct structura
          {
	           int pos,val;
           };
           .....
           
           ifstream f("inv.in");
	f>>n;
	int i;
	structura sort[100000];
	for(i=0;i<n;++i)
	{f>>v[i];sort[i].val=v[i];sort[i].pos=i;}
	f.close();
	qsort(sort,n,sizeof(structura),cmp);
	int ct=0;
	for(i=0;i<n;++i)
	{
		if(sort[i].val!=sort[i-1].val)++ct;
		v[sort[i].pos]=ct;
	}

Multumesc anticipat!