Cod sursa(job #812573)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 13 noiembrie 2012 23:43:39
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include <fstream.h>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

int v[500001], dq[500001];

int main()
{   
	int maxim=-32000, stop, start, n, k, i, p=1, u=0;
	
	f>>n>>k;
	
	for(i=1;i<=n;++i)
	{
		f>>v[i];
		
		while(p<=u&&v[i]<=v[dq[u]])
			--u;
		
		dq[++u]=i;
		
		if(i-dq[p]==k)
			++p;
		
		if(i>=k&&v[dq[p]]>maxim)
		{  
			maxim=v[dq[p]];
			start=dq[p-1]+1;
			stop=i;
		}
	}
	g<<start<<" "<<stop<<" "<<maxim;
	return 0;
}