Cod sursa(job #74540)

Utilizator zobicaMarin Marin zobica Data 26 iulie 2007 02:29:43
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>

using namespace std;

int a[5000000], d[5000000];
long k, n, p = -1, u = -1, pi = 1, ps = 1, vmin;

void add_deque(int poz) {
	if (p == -1)
		p = 0;
	d[++u] = poz;
}

void citire(){
	ifstream fin("secventa.in");
	fin >> n >> k;
	for (int i=0;i<n;i++)
		fin >> a[i];
	fin.close();
}

void rezolva() {
	add_deque(0);
	if (k == 1)
		vmin = a[0];
	else
		vmin = -32767;
	for (int i = 1; i < n ; i++) {
		while (p <=u && d[p] <= i - k) p++;
		while (p <=u && a[d[u]] >= a[i]) u--;
		add_deque(i);
		if ( i >= k - 1 && a[d[p]] > vmin ){
			vmin = a[d[p]];
			pi = i-k+1;
			ps = i;
		}	
	}
}

void scrie(){
	ofstream fout("secventa.out");
	fout << pi + 1 << " " << ps + 1 << " " << vmin;
	fout.close();
}

int main() {
	citire();
	rezolva();
	scrie();
	return 0;
}