Cod sursa(job #681924)

Utilizator geobarosanu1Tutuianu George geobarosanu1 Data 18 februarie 2012 10:32:20
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define max 123457;
using namespace std;

vector <unsigned int> lista;

bool search(vector <pair <unsigned int, int>> hash[123458],unsigned int x, int cheie){

	for (int j=0;j<hash[cheie].size();j++)
		if (hash[cheie][j].first==x && hash[cheie][j].second!=0)
				return 1;
	return 0;
};
int calculare(int secventa_cautata){

	vector <pair <unsigned int, int>> hash[123458];
	queue <unsigned int> coada;
	int solutie=0,lungime=0,cheie;

	for (int i=0;i<lista.size();i++){
		
		cheie=lista[i]%max;
		if (!search(hash,lista[i],cheie)){

			if (lungime<secventa_cautata){
				///////////// adauga un element //////////////
				hash[cheie].push_back(make_pair(lista[i], 1));
				lungime++;
				coada.push(lista[i]);
				//////////////////////////////////////////////
				if (lungime == secventa_cautata)
					solutie++;
			}	//	elementul nu se gaseste in coada si lungimea subsirului este mai mica

			else {
				while (lungime >= secventa_cautata){
					int x=coada.front();
					coada.pop();
					//////// Elimina un element ////////
					for (int j=0;j<hash[cheie].size();j++)
						if (hash[cheie][j].first==x){
							hash[cheie][j].second--;
							if (!hash[cheie][j].second){
								lungime--;
								hash[cheie][j].first=0;
							}
							continue;
						}
					////////////////////////////////////
					if (lungime == secventa_cautata)
						solutie++;
				}	// end_while -- lungimea a devenit mai mica
				coada.push(lista[i]);
				lungime++;
				hash[cheie].push_back(make_pair(lista[i],1));
				solutie++;
			}	// end_if_else elementul nu se gaseste in coada si lungimea este egala
		}	// end_if_then -- elementul nu se gaseste in coada

		else {
			coada.push(lista[i]);
			for (int j=0;j<hash[cheie].size();j++)
				if (hash[cheie][j].first==lista[i]){
					hash[cheie][j].second++;
					continue;
				}
			solutie++;

		}

	}
	
	return solutie;
}

int main()
{
	freopen("secv5.in","r",stdin);
	freopen("secv5.out","w",stdout);
	int n,l,u;
	unsigned int x;

	scanf("%d%d%d", &n, &l, &u);
	while (n--){
		scanf("%d", &x);
		lista.push_back(x);
	}
	
	l=calculare(l);
	u=calculare(u);
	printf("%d", l-u);

	return 0;
}