Pagini recente » Borderou de evaluare (job #860153) | Cod sursa (job #14015)
Cod sursa(job #14015)
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
#define sz(a) int((a).size())
const int Nmax = 1048576;
const unsigned int r = 2654435761u;
const int Tmax = 196613;
int i, j, n, l, u, ct, h, st, dr;
long long sol;
unsigned int sir[Nmax], vl;
vector<int> t[Tmax];
int s[Nmax], v[Nmax];
inline void citire()
{
scanf("%d %d %d\n", &n, &l, &u);
for (i=1; i<=n; ++i)
scanf("%u", &sir[i]);
}
inline long long solve2(int m)
{
long long ret = 0;
st = 1;
ct = 0;
for (dr=1; dr<=n; ++dr)
{
if (!v[s[dr]])
++ct;
++v[s[dr]];
while (ct > m)
{
if (!(--v[s[st]]))
--ct;
++st;
}
ret += dr - st + 1;
}
for (; st<=n; ++st)
--v[s[st]];
return ret;
}
inline int find(int x)
{
int size = sz(t[h]), vl = sir[x];
vector<int> :: iterator it;
for (it = t[h].begin(); it != t[h].end(); ++it)
if (vl == sir[*it])
{
s[x] = s[*it];
return 1;
}
return 0;
}
inline void solve()
{
int i;
for (i=1; i<=n; ++i)
{
h = (sir[i] * r) % Tmax;
if (!find(i))
{
t[h].pb(i);
s[i] = ++ct;
}
}
sol = solve2(u) - solve2(l-1);
printf("%lld\n", sol);
}
int main()
{
freopen("secv5.in", "r", stdin);
freopen("secv5.out", "w", stdout);
citire();
solve();
return 0;
}