Referred Anudeep Nekkanti’s blogpost to write the solution in Java but I’m getting WA.
SPOJ DQUERY problem link
Anudeep’s blogpost
Here’s my code:
import java.io.*;
import java.util.*;
class Pair<T, U, V>
{
T f;
U s;
V i;
public Pair(T Integer1, U Integer2, V i)
{
f=Integer1; s=Integer2;this.i=i;
}
T first()
{
return f;
}
U second()
{
return s;
}
V geti()
{
return i;
}
}
class Main
{
static int[] a, counter, ans;
static int n, count;
static int BLOCK;
static void add(int index)
{
if(counter[a[index]] == 0)
count++;
}
static void remove(int index)
{
if(counter[a[index]] == 1)
count--;
}
public static void main(String[] args) throws Exception
{
Scanner sc= new Scanner(System.in);
int n= sc.nextInt();
Main.n =n;
BLOCK=(int)Math.sqrt(n);
a= new int[n+2];
for(int i=1; i<=n; i++)
{
a[i]= sc.nextInt();
}
int q= sc.nextInt();
ans= new int[q];
List<Pair<Integer, Integer, Integer>> list= new ArrayList<Pair<Integer, Integer, Integer>>();
for(int k=0; k<q; k++)
{
list.add(new Pair<Integer, Integer, Integer>(sc.nextInt(), sc.nextInt(),k));
}
list.sort(new Comparator<Pair<Integer, Integer, Integer>>() {
@Override
public int compare(Pair<Integer, Integer, Integer> o1, Pair<Integer, Integer, Integer> o2) {
if (o1.first()/BLOCK > o2.first()/BLOCK)
{
return 1;
}
else if ((o1.first()/BLOCK) == (o2.first()/BLOCK))
{
if(o1.second() > o2.second())
return 1;
else
return -1;
}
else
{
return -1;
}
}
});
counter= new int[3000000];
int currentL=1, currentR=1;
for(int m=0;m<q;m++)
{
while(currentL < list.get(m).first())
{
remove(currentL);
counter[a[currentL]]--;
currentL++;
}
while(currentL >= list.get(m).first())
{
add(currentL);
counter[a[currentL]]++;
currentL--;
}
while(currentR > list.get(m).second())
{
remove(currentR);
counter[a[currentR]]--;
currentR--;
}
while(currentR <= list.get(m).second())
{
add(currentR);
counter[a[currentR]]++;
currentR++;
}
ans[list.get(m).geti()]= count;
}
for(int m=0;m<q;m++)
{
System.out.println(ans[m]);
}
}
}
My code passes the test for sample input and for
1
1
1
1 1
it gives answer 1 which I think is correct.