the array. just array of integer. int a[N];
but i have used vector<int> v[N];
array of dynamic arrays.
each number in first array in input we must associate with
some smaller number from 1 to N
for this purpose i have used map<int, int> but it can be hashtable, hashmap or just another array + binary search.

Forum says that 1613 most interesting problem in last list.
This is because sorting one of the most fundamental idea in
algorithmics. Concerning to this problem my advise:
struct data{
int val;
int num;
};
bool operator <(struct data d1,struct data d2)
{
if (d1.val<d2.val)return 1;
if (d2.val<d1.val)return 0;
if (d1.num<d2.num) return 1;
return 0;
}
After that we should make qsort, leftmost and right most
binary search and so on.
More exactly:
Let l r x- inqure;
and
i1=leftmost(l,x);
i2=rightmost(r,x);
if ((i1!=-1)&&(i2!-1)&&(i1<i2)&&(data[i1]==x)&&(data[i2])==x)- Ok



Edited by author 04.04.2008 23:08

I used map and vector with stl sort function got AC, but my solution time is 0.6s then I try to solve it by hash table with Double hash key, but i can't improve the time, and i got .91s. i increas the array lenghts to 2pow17 and hash key
is : key% (2pow17-1)   // it's prime
rh  key is: (i+(1+key% (2pow17-2) ) % (2pow17-1)

but it appear that isn't good way.

plz tell me your solutions with high performance