Cod sursa(job #383276)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 16 ianuarie 2010 11:24:06
Problema Secventa 5 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;

int n,u,l,nr,f[1<<20];
unsigned int v[1<<20],v2[1<<20];
ll spsecv(int lim)
{
    int nrdif=0,i;
    int st=-1;
    ll sol=0;
    for(i=0;i<n;i++)
    {
        if(!f[v[i]])
            nrdif++;
        f[v[i]]++;
        while(st<i && nrdif>lim)
        {
            st++;
            f[v[st]]--;
            if(!f[v[st]])
                nrdif--;                
        }
        sol+=i-st;
    }
    return sol;
}

char s[16];
int main ()
{
    int i,j,len,st,dr,m=0,nrel=0,ult;
    ll r1,r2,r;
    freopen("secv5.in","r",stdin);
    freopen("secv5.out","w",stdout);
    scanf("%d%d%d\n",&n,&l,&u);
    for(i=0;i<n;i++)
    {
        fgets(s,sizeof(s),stdin);
        int len=strlen(s);
        for (j=0,len=strlen(s);j<len;j++)
            if (s[j]>='0' && s[j]<='9')
                v[i]=v[i]*10+s[j]-'0';
            else
                break;
        v2[i]=v[i];
    }
    sort(v2+0,v2+n);
    ult=-1;
    for(i=0;i<n;i++)
        if(v2[i]!=ult)
        {
            v2[nrel++]=v2[i];
            ult=v2[i];
        }
    for(i=0;i<n;i++)
    {
        st=0;
        dr=nrel-1;
        while(st<=dr)
        {
            m=(st+dr)/2;
            if(v2[m]<v[i])
                st=m+1;
            else
                if(v2[m]>v[i])
                    dr=m-1;
                else
                    break;
        }       //cautare binara
        v[i]=m;
    }
    r1=spsecv(u);
    for(i=0;i<nrel;i++)
        f[i]=0;
    r2=spsecv(l-1);
    r=r1-r2;
    printf("%lld\n",r);
    return 0;
}