Cod sursa(job #1838104)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 31 decembrie 2016 00:15:14
Problema Secventa 5 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <cstdio>
#include <unordered_map>
#define MAXN (1<<21)

using namespace std;

int n, L, U;
unsigned int a[MAXN];
long long sol;

long long tot(int ma)
{
	unordered_map<unsigned int, int> m;
    int sz = 0, ind = 1;
    long long part = 0;
    for (int i = 1; i <= n; i++)
	{
		int v = (++m[a[i]]);
        if (v==1) ++sz;
        for (; sz > ma; ind++)
		{
            v = (--m[a[ind]]);
            if (v == 0)
                sz--;
		}
		part += i-ind+1;
	}
	return part;
}

void solve()
{
	sol = tot(U) - tot(L-1);
}

int main()
{
    freopen("secv5.in", "r", stdin);
    freopen("secv5.out", "w", stdout);

    cin >> n >> L >> U;
    for (int i = 1; i <= n; i++)
		cin >> a[i];
	solve();
	printf("%lld\n", sol);

    return 0;
}