Cod sursa(job #1062167)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 20 decembrie 2013 19:58:03
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

struct elem
{
    long long int val;
    int poz;
}v[1048580];
long long int m[1048580];

bool operator<(const elem &a,const elem &b)
{
    if(a.val>b.val)
       return 0;
    return 1;
}

#define lsb(i) (i&(-i))

long long int aib[1048580];

long long int sum(long long int poz)
{
    //cout<<"sum("<<poz<<")="<<endl;
    long long int s=0;
    for(;poz>0;poz-=lsb(poz))
    {
        //cout<<"poz="<<poz<<endl;
        s+=aib[poz];
    }
    return s;
}

long long int n;

void update(long long int poz,long long int val)
{
    for(;poz<=n;poz+=lsb(poz))
        aib[poz]+=val;
}

long long int l,u;
long long int caut_bin(long long int x)
{
    long long int st=1,dr=x,mijl=(x+1)>>1;
    long long int rasp1=x+1;
    long long int aux;

    //cout<<"u="<<u<<' '<<"l="<<l<<endl;
    while(st<=dr)
    {
        //cout<<"st1="<<st<<' '<<"dr1="<<dr<<' '<<"mijl1="<<mijl<<endl;
        aux=sum(x)-sum(mijl-1);
        //cout<<"aux="<<aux<<endl;
        //cout<<"ce-i asta?"<<endl;
        if(aux<=u)
        {
            if(mijl<rasp1)
                rasp1=mijl;
            dr=mijl-1;
        }
        else
            st=mijl+1;
        //cout<<"ce sa-i facei"<<endl;
        mijl=(st+dr)>>1;
        //cout<<"acum "<<"st1="<<st<<' '<<"dr1="<<dr<<' '<<"mijl1="<<mijl<<endl;
        //cout<<"adsasdasd"<<endl;
    }
    //cout<<"rasp1="<<rasp1<<endl;

    st=1;
    dr=x;
    mijl=(x+1)>>1;
    long long int rasp2=-1;
   // cout<<"aici"<<endl;
    while(st<=dr)
    {

     //   cout<<"st2="<<st<<' '<<"dr2="<<dr<<' '<<"mijl2="<<mijl<<endl;
        aux=sum(x)-sum(mijl-1);
        if(aux>=l)
        {
            if(mijl>rasp2)
                rasp2=mijl;
            st=mijl+1;
        }
        else
            dr=mijl-1;
        mijl=(st+dr)>>1;
    }
    if(rasp2<rasp1)
        return 0;
    else
    {
      //  cout<<"rasp2="<<rasp2<<' '<<"rasp1="<<rasp1<<endl;
        return (rasp2-rasp1+1);
    }
}


long long int data[1048580];

int main()
{
    ifstream cin("secv5.in");
    ofstream cout("secv5.out");

    long long int i;
    cin>>n>>l>>u;
    for(i=1;i<=n;i++)
    {
        cin>>m[i];
        v[i].val=m[i];
        v[i].poz=i;
    }
    sort(v+1,v+n+1);

    long long int ante=0;
    long long int curent=0;
    for(i=1;i<=n;i++)
    {
        if(ante!=v[i].val)
        {
            ante=v[i].val;
            curent++;
        }
        m[v[i].poz]=curent;
    }


    long long int s=0;


    memset(data,-1,sizeof(data));

    for(i=1;i<=n;i++)
    {
        //cout<<"i="<<i<<endl;
        //if(data[m[i]]!=-1)
        //    ;//update(data[m[i]],-1);
        //cout<<"da"<<endl;
        //update(i,1);
        //data[m[i]]=i;
        data[m[i]]=i;
        //cout<<"nu"<<endl;
        //s+=caut_bin(i);
        //cout<<"ups"<<endl;
    }

    //cout<<s<<'\n';

    cin.close();
    cout.close();
    return 0;
}