Pagini recente » Cod sursa (job #203470) | Cod sursa (job #885791) | Cod sursa (job #556670) | Istoria paginii runda/simulare-cartita-15a/clasament | Cod sursa (job #216856)
Cod sursa(job #216856)
#include <stdio.h>
#include <string.h>
unsigned int n, l, u, v[1500000], nr, rez1, rez2, rez;
typedef struct nod
{
unsigned int x, ap;
nod *a;
} *pNod;
pNod hash[700000];
unsigned int hash_function(unsigned int x)
{
return x % 666013;
}
unsigned int caut(unsigned int x)
{
unsigned 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(unsigned int x)
{
unsigned 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(unsigned int x)
{
unsigned int poz = hash_function(x);
pNod q, p;
for (q = hash[poz]; q -> x != x; q = q -> a);
q -> ap--;
if (q -> ap == 0)
{
if (hash[poz] -> x == x) hash[poz] = hash[poz] -> a;
else
{
for (p = hash[poz]; p -> a -> x != x; p = p -> a);
p -> a = p -> a -> a;
}
nr--;
}
}
void citire()
{
freopen("secv5.in","r",stdin);
freopen("secv5.out","w",stdout);
unsigned 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';
}
}
unsigned int main()
{
citire();
unsigned 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;
}