Cod sursa(job #3121254)

Utilizator daristyleBejan Darius-Ramon daristyle Data 11 aprilie 2023 12:54:13
Problema Secventa 5 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>

using namespace std;

ifstream fin("secv5.in");
ofstream fout("secv5.out");

const int MOD_MAX = 666013;
const int N_MAX = 1024 * 1024;
unsigned int v[N_MAX];

struct element {
		unsigned int num;
		int freq;
};

class HashTable {
private:
		const int NIL = -1;
		int head[MOD_MAX];
		element key[N_MAX];
		int nxt[N_MAX];
		int mod;
		int curr;

public:
		HashTable(int modulo) {
			mod = modulo;

			curr = 0;
			for(int i = 0; i < mod; ++i)
				head[i] = NIL;
			for(int i = 0; i < N_MAX; ++i)
				nxt[i] = NIL;
		}

		void init(int modulo) {
			mod = modulo;

			curr = 0;
			for(int i = 0; i < mod; ++i)
				head[i] = NIL;
			for(int i = 0; i < N_MAX; ++i){
				nxt[i] = NIL;
				key[i].freq = 0;
			}
		}

		int getkey(unsigned int x) {
			return x % mod;
		}

		int add(unsigned int x) {
			int list = getkey(x);
			int it = head[list];
			int retval = 0;
			while(it != NIL && key[it].num != x)
				it = nxt[it];
			if(it != NIL)
				++key[it].freq;
			else{
				key[curr].num = x;
				key[curr].freq = 1;
				nxt[curr] = head[list];
				head[list] = curr;
				++curr;
				retval = 1;
			}

			return retval;
		}

		bool find(unsigned int x) {
			int list = getkey(x);
			int it = head[list];
			while(it != NIL && key[it].num != x)
				it = nxt[it];

			return it != NIL;
		}

		int erase(unsigned int x) {
			int list = getkey(x);
			int ant = head[list], it = nxt[ant];
			int retval = 0;
			if(key[ant].num == x){
				--key[ant].freq;
				if(!key[ant].freq){
					head[list] = nxt[ant];
					retval = 1;
				}
			}else{
				while(it != NIL && key[it].num != x){
					ant = it;
					it = nxt[it];
				}

				if(it != NIL){
					--key[it].freq;
					if(!key[it].freq){
						nxt[ant] = nxt[it];
						retval = 1;
					}
				}
			}

			return retval;
		}

};

HashTable ht(0);

long long cntSecv(unsigned int v[], int n, int x) {
	ht.init(MOD_MAX);
	int distinct_elements = 0, left = 0;
	long long nr_secv = 0;
	for(int right = 0; right < n; ++right){
		distinct_elements += ht.add(v[right]);

		while(left <= right && distinct_elements > x)
			distinct_elements -= ht.erase(v[left++]);

		nr_secv += (long long) right - left + 1;
	}

	return nr_secv;
}

int main() {
	int n, l, u;
	fin >> n >> l >> u;
	for(int i = 0; i < n; ++i)
		fin >> v[i];

	fout << cntSecv(v, n, u) - cntSecv(v, n, l - 1) << '\n';

	fin.close();
	fout.close();
	return 0;
}