Cod sursa(job #9363)

Utilizator diac_paulPaul Diac diac_paul Data 27 ianuarie 2007 14:58:49
Problema Secventa 5 Scor 0
Compilator c Status done
Runda Unirea 2007, clasele 11-12 Marime 0.93 kb
#include <stdio.h>

#define NMax 1050000

FILE *fin, *fout;

long n, l, u, a[NMax], d[NMax], nr[NMax];
long long rez;

void read()
{
	long i;
	fin = fopen("secv5.in", "rt");
	fout = fopen("secv5.out", "wt");

	fscanf(fin, "%ld %ld %ld", &n, &l, &u);

	for (i = 0; i < n; i++)
		fscanf(fin, "%ld", &a[i]);
	fclose(fin);
}

void solve()
{
	long i, j, k, p;

	for (i = 0; i < n; i++)
	{
		// secventele [0, i]

		p = -1;
		for (j = i-1; j>=0; j--)
			if (a[j] == a[i])
			{
				p = j;
				break;
			}
		/*
		             p               i
		 o o o o o o X o o o o o o o X
		 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
		*/

		for (k = 0; k <= p; k++) nr[d[k]]++;
		for (; k <= i; k++) nr[++d[k]]++;
	}
	for (i = l; i <= u; i++)
		rez += nr[i];
}

void show()
{
	fout = fopen("secv5.out", "wt");
	fprintf(fout, "%lld\n", rez);
	fclose(fout);
}

int main()
{
	read();
	solve();
	show();

	return 0;
}