Pagini recente » Cod sursa (job #2762210) | Cod sursa (job #645257) | Cod sursa (job #1973209) | Cod sursa (job #2522412) | Cod sursa (job #383276)
Cod sursa(job #383276)
#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;
}