Cod sursa(job #344170)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 august 2009 20:39:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
//secventa.cpp
#include <fstream>
#define DIM 2<<18
int a[DIM],n,k,p,u,d[DIM],end,i;
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
void solve()
{   
	p=1;
	int min=-300000;
	fin >> n >> k;
	for (i = 1; i <= n; ++i) fin >> a[i];
    for (i = 1; i <= n; ++i)
	{   
		while (p <= u && a[i] <= a[ d[u] ]) --u;
		d[ ++u ] = i;
		if (i - d[p] == k) ++p;
        if (i >= k && a[ d[p] ] > min)
		   {
			   min = a[ d[p] ];
			   end = i;
		   }
	}
fout<<end-k+1<<" "<<end<<" "<<min;
}			
int main()
{
	solve();
	return 0;
}
//sper sa ne mai vedem...