Pagini recente » Cod sursa (job #2990084) | Cod sursa (job #2607328) | Cod sursa (job #2611890) | Cod sursa (job #2813644) | Cod sursa (job #117439)
Cod sursa(job #117439)
#include <cstdio>
#include <memory.h>
#include <list>
using namespace std;
const char iname[] = "secv5.in";
const char oname[] = "secv5.out";
#define MAXN 1048576
#define HASH_SIZE 1048576
typedef long long i64;
const unsigned int hash_prime = 666777;
struct hash_node {
unsigned int key;
int new_key;
hash_node *next;
hash_node(unsigned int key, int new_key) {
this -> key = key;
this -> new_key = new_key;
}
} ;
list <hash_node> hash_map[HASH_SIZE];
list <hash_node>::iterator it;
inline unsigned int h(const unsigned int key) {
return (key * hash_prime) >> 12;
}
void hash_in(unsigned int key, int new_key) {
hash_map[h(key)].push_back(hash_node(key, new_key));
}
int hash_out(unsigned int key)
{
unsigned int n = h(key);
for (it = hash_map[n].begin(); it != hash_map[n].end(); ++ it)
if (it -> key == key) return it -> new_key;
return 0;
}
int N, L, U;
unsigned int A[MAXN];
int B[MAXN], Cnt[MAXN];
i64 f(const int X)
{
if (X == 0)
return 0;
memset(Cnt, 0, sizeof(Cnt));
i64 ans = 0;
for (int i = 0, head = 0, cnt = 0; i < N; ++ i) {
cnt += ((++ Cnt[B[i]]) == 1);
while (cnt > X) {
cnt -= ((-- Cnt[B[head]]) == 0);
head ++;
}
ans += (i64)(i-head+1);
}
return ans;
}
int main(void)
{
freopen(iname, "r", stdin);
freopen(oname, "w", stdout);
int key = 0, hashout;
scanf("%d %d %d", &N, &L, &U);
for (int i = 0; i < N; ++ i)
{
scanf("%u", &A[i]);
hashout = hash_out(A[i]);
if (!hashout)
hash_in(A[i], (++ key)), B[i] = key;
else
B[i] = hashout;
}
printf("%lld\n", f(U) - f(L - 1));
return 0;
}