Cod sursa(job #216830)
#include <stdio.h>
#include <string.h>
int n, l, u, v[1500000], nr, rez1, rez2, rez;
typedef struct nod
{
int x, ap;
nod *a;
} *pNod;
pNod hash[700000];
int hash_function(int x)
{
return x % 666013;
}
int caut(int x)
{
int xx = hash_function(x);
for (pNod p = hash[xx]; p != NULL; p = p -> a)
if (p -> x == x) return 1;
return 0;
}
void add(int x)
{
int poz = hash_function(x);
pNod q;
if (!caut (x))
{
q = new nod;
q -> x = x;
q -> ap = 1;
q -> a = hash[poz];
hash[poz] = q;
nr++;
}
else
{
for (q = hash[poz]; q -> x != x; q = q -> a);
q -> ap++;
}
}
void sterg(int x)
{
int poz = hash_function(x);
pNod q, p;
q = hash[poz];
for (; q -> x != x; q = q -> a);
if (q != hash[poz])
for (p = hash[poz]; p -> a != q; p = p -> a);
else p = q;
if (q -> ap > 1) q -> ap--;
else
{
p = q -> a;
nr--;
}
}
void citire()
{
freopen("secv5.in","r",stdin);
freopen("secv5.out","w",stdout);
int i, j;
char s[100];
scanf("%d %d %d\n",&n,&l,&u);
for (i = 1; i <= n; i++)
{
scanf("%s",&s);
j = 0;
while (s[j] <= '9' && s[j] >= '0') v[i] = v[i] * 10 + s[j++] - '0';
}
}
int main()
{
citire();
int i, j;
j = 0;
for (i = 1; i <= n; i++)
{
add(v[i]);
if (nr >= l)
while (nr >= l)
{
j++;
sterg(v[j]);
}
rez1 += j;
}
for (i = 1; i <= n; i++) hash[i] = NULL;
nr = 0;
j = 0;
for (i = 1; i <= n; i++)
{
add(v[i]);
if (nr >= u + 1)
while (nr >= u + 1)
{
j++;
sterg(v[j]);
}
rez2 += j;
}
rez = rez1 - rez2;
printf("%d\n",rez);
return 0;
}