red_coder's blog

By red_coder, 11 years ago, In English

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);
    }
}


  • Vote: I like it
  • -26
  • Vote: I do not like it