Cod sursa(job #415162)

Utilizator otilia_sOtilia Stretcu otilia_s Data 10 martie 2010 22:52:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
using namespace std;
const int NMAX=500003;
const int minf=-30005;
int a[NMAX],dq[NMAX];

int main()
{
	ifstream fin("secventa.in");
	int n,k,i,fr,bk,pbaza,Max;
	fin>>n>>k;
	fr=1; bk=0;
	for (i=1;i<k;++i)
	{
		fin>>a[i];
		while (fr<=bk && a[i]<=a[dq[bk]]) bk--;
		dq[++bk]=i;
	}
	pbaza=0; Max=minf;
	for (;i<=n;++i)
	{
		fin>>a[i];
		while (fr<=bk && a[i]<=a[dq[bk]]) bk--;
		dq[++bk]=i;
		if (dq[fr]==i-k) ++fr;
		if (a[dq[fr]]>Max){Max=a[dq[fr]]; pbaza=i;}
	}
	fin.close();
	
	ofstream fout("secventa.out");
	fout<<pbaza-k+1<<" "<<pbaza<<" "<<Max;
	fout.close();
	return 0;
}