Pagini recente » Cod sursa (job #2054351) | Cod sursa (job #830424) | Cod sursa (job #2945637) | Cod sursa (job #1755586) | Cod sursa (job #2681583)
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = (1 << 20) + 5;
const int MOD = 666013;
struct secv
{
unsigned x;
int y;
secv(unsigned tx = 0 , int ty = 0): x(tx) , y(ty){}
};
vector <secv> h[MOD + 5];
void clearh()
{
for(int i = 0 ; i < MOD ; ++ i)
h[i].clear();
}
void inserth(unsigned x)
{
h[x % MOD].push_back({x, 1});
}
int findh(unsigned x)
{
int i, key = x % MOD;
for(i = 0 ; i < h[key].size() ; i ++)
if(h[key][i].x == x)
return h[key][i].y;
return -1;
}
void updateh(unsigned x, int val)
{
int i, key = x % MOD;
for(i = 0 ; i < h[key].size() ; i ++)
if(h[key][i].x == x)
h[key][i].y += val;
}
void eraseh(unsigned x)
{
int key = x % MOD;
vector <secv>::iterator it;
for(it = h[key].begin() ; it != h[key].end() ; it ++)
if((*it).x == x)
{
h[key].erase(it);
return;
}
}
unsigned v[NMAX + 5];
long long secv(int n, int lim)
{
if(lim == 0)
return 0;
int st, dr, cnt;
long long nr = 0;
clearh();
cnt = 0;
for(st = dr = 1 ; dr <= n ; ++ dr)
{
if(findh(v[dr]) != -1)
updateh(v[dr], 1);
else
{
inserth(v[dr]);
++ cnt;
}
while(cnt > lim)
{
updateh(v[st], -1);
if(findh(v[st]) == 0)
{
eraseh(v[st]);
-- cnt;
}
++ st;
}
nr += (dr - st + 1);
}
return nr;
}
int main()
{
freopen("secv5.in", "r", stdin);
freopen("secv5.out", "w", stdout);
int n, i, l, u;
scanf("%d%d%d" , &n , &l , &u);
for(i = 1 ; i <= n ; ++ i)
scanf("%u" , &v[i]);
printf("%lld\n", secv(n, u) - secv(n, l - 1));
return 0;
}