Cod sursa(job #857880)

Utilizator deneoAdrian Craciun deneo Data 18 ianuarie 2013 13:49:57
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda ichb-locala-2013-10 Marime 1.08 kb
#include <fstream>
#include <iostream>
using namespace std;

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

#define MAXN 1 << 21

int N, L, U;
int sir[MAXN], aib[MAXN], s[MAXN];

void set_aib() {
	for (int i = 0; i <= N; ++i)
		aib[i] = 1;
}

void insert_aib(int poz, int elem) {
	while(poz <= N) {
		aib[poz] *= elem;
		poz += poz & (-poz);
	}
}

int get_aib(int poz) {
	int prod = 1;
	while (poz > 0) {
		prod *= aib[poz];
		poz -= poz & (-poz);
	}
	return prod;
}

int get_secv(int st, int fn) {
	return get_aib(fn) / get_aib(st - 1);
}

int main() {
	fin >> N >> L >> U;
	
	for (int i = 1; i <= N; ++i)
		fin >> s[i];
	
	for (int i = 1; i <= N; ++i) {
		sir[++sir[0]] = 1;
		while (s[i] == s[i + 1]) {
			++sir[sir[0]];
			++i;
		}
	}
	
	set_aib();
	
	for (int i = 1; i <= sir[0]; ++i)
		insert_aib(i, sir[i]);
	
	int sum = 0, rez = 0;
	
	for (int i = L; i <= sir[0]; ++i) {
		sum += get_secv(i - L + 1, i - 1);
		if (i > U) 
			sum -= get_secv(i - U, i - 1);
		sum *= sir[i];
		rez += sum;
	}
	
	fout << rez;
	
	return 0;
}