Cod sursa(job #1521524)

Utilizator binicBinica Nicolae binic Data 10 noiembrie 2015 16:49:59
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
/*
#include <cstdio>
#define LSB(x) ((-x)&x)
using namespace std;

int x,N,M,i,aib[100005],t,a,b;
void Update(int V,int Pos)
{
    int i;
    for(i=Pos;i<=N;i=i+LSB(i))
            aib[i]=aib[i]+V;
}

int Suma(int Pos)
{
    int i,s=0;
    for(i=Pos; i>0; i-=LSB(i))
            s=s+aib[i];
    return s;
}

int query(int P1,int P2)
{
    return (Suma(P2)-Suma(P1-1));
}


int verific_binar(int a)
{
    int m,p,u;
    p=1;
    u=N;
    while (p<=u)
        {
             m=(p+u)/2;
             if (Suma(m)==a) return m;
             else
             if (Suma(m)<a)
                {
                    if (Suma(m+1)>a) return -1;
                    else
                        p=m+1;
                }
            else
            {
                if(Suma(m-1)<a) return -1;
                else u=m-1;
            }
        }
    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&N,&M);
    for( i = 1; i <= N; i++ )
    {
        scanf("%d",&x);
        Update(x,i);
    }
    while(M>0)
    {
        M--;
        scanf("%d",&t);
        if ( t==0 )
        {
                scanf("%d%d\n",&a,&b);
                Update( b, a );
        }
        else
        if (t==1)
        {
                scanf("%d%d\n",&a,&b);
                printf("%d\n",query(a,b));
        }
        else
        {
                scanf("%d\n",&a);
                printf("%d\n",verific_binar(a));
        }
    }
    return 0;
}*/

#include<cstdio>
#include<map>
#define LSB(x)  (x&(-x))
using namespace std;
int n,i,p;
long long ma,ras,s[1000004];
map <  long long  , int > aib;
void update(long long x)
{
    while(x<=ma)
    {
        aib[x]++;
        x+=LSB(x);
    }
}
int Query(long long x)
{
    long long ras=0;
    for(long long i=x;i>0;i-=LSB(i))
        if(aib.count(i))ras+=aib[i];
    return ras;
}
int main()
{
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    scanf("%d",&n);
    ma=1000000000LL*1000000LL;
    for(i=1;i<=n;i++)
        scanf("%lld",&s[i]);
    scanf("%d",&p), s[0]=ma;
    for(i=1;i<=n;i++)
    {
        s[i]-=p;
        s[i]=s[i-1]+s[i];
    }
    ma=ma*2LL;
    update(s[n]);
    ras=1;
    for(i=n-1;i>=0;i--)
    {
        ras+=Query(s[i]);
        update(s[i]);
    }
    printf("%lld",ras);
    return 0;
}