Cod sursa(job #3121137)

Utilizator daristyleBejan Darius-Ramon daristyle Data 10 aprilie 2023 21:07:59
Problema Secventa 5 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>

using namespace std;

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

const int MOD_MAX = 666013;
const int N_MAX = (1 << 20);
int v[N_MAX];

struct element {
		int num;
		int freq = 0;
};

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

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

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

		int getkey(int x) {
			while(x < 0) x += mod;
			return x % mod;
		}

		int add(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(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(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(MOD_MAX);

int main() {
	int n, l, u;
	fin >> n >> l >> u;
	int add = 0, erase = 0, cnt_elem = 0, start = 0;
	long long nr_secv = 0;
	while(add < n){
		if(cnt_elem <= u){
			fin >> v[add];
			cnt_elem += ht.add(v[add++]);
		}else{
			nr_secv += erase - start + 1;
			cnt_elem -= ht.erase(v[erase++]);
			start = erase;
		}
	}
	nr_secv += n - start;

	fout << nr_secv << '\n';

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