hey guys i tried to solve this simple spoj Problem using Binary Indexed Trees. I tested all possible cases on my computer and its giving right answer for every case. But its giving wrong answer on spoj. Can u figure out the error. here is my code
/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
typedef long long LL;
string inttostring(int n)
{
stringstream a;
a<<n;
return a.str();
}
int stringtoint(string A)
{
istringstream a(A);
int p;
a>>p;
return p;
}
//////////////////////////////////////////////////////
struct E
{
int i,j,rank,time;
};
struct AA
{
int val;
int time;
};
bool cmp(const E& a,const E& b)
{
return a.rank<b.rank;
}
bool cmp2(const AA& a,const AA& b)
{
return a.time<b.time;
}
E eve[250000];
int tree[30005];
int his[1000005];
int n;
int read(int idx){
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(int idx ,int val){
while (idx <= n+5){
tree[idx] += val;
idx += (idx & -idx);
}
}
int main()
{
si(n);
int A[n];
f(i,0,n)
{
si(A[i]);
eve[i].i=A[i];
eve[i].j=-1;
eve[i].rank=i+1;
eve[i].time=0;
}
int q,a,b;
si(q);
f(i,0,q)
{
si(a); si(b);
eve[i+n].i=a;
eve[i+n].j=b;
eve[i+n].rank=b;
eve[i+n].time=i;
}
sort(eve,eve+n+q,cmp);
AA ans[q+5];
int u=0;
f(i,0,n+q)
{
if(eve[i].j==-1)
{
if(his[eve[i].i])
{
update(his[eve[i].i],-1);
}
his[eve[i].i]=eve[i].rank;
update(his[eve[i].i],1);
}
else
{
ans[u].val=read(eve[i].j)-read(eve[i].i-1);
ans[u++].time=eve[i].time;
}
}
sort(ans,ans+u,cmp2);
f(i,0,u)
{
printf("%d\n",ans[i].val);
}
}