Cod sursa(job #492042)

Utilizator crushackPopescu Silviu crushack Data 13 octombrie 2010 11:43:25
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#define NMax 500005
using namespace std;

const char IN[]="secventa.in",OUT[]="secventa.out";

int N,K;
int x,y,Max=-1;
int a[NMax],D[NMax],first,last;

int main()
{
	int i;
	ifstream fin(IN);
	fin>>N>>K;
	for (i=0;i<N;i++)
		fin>>a[i];
	fin.close();
	
	for (i=0;i<N;i++)
	{
		while (first<=last && (a[i]<a[D[last]] || i-D[last]>=K))
			last--;
		D[++last]=i;
		while (first<=last && i-D[first]>=K)
			first++;
		if (i==K-1)
			Max=a[D[first]],x=0,y=K-1;
		if (i>=K && a[D[first]]>Max)
			Max= a[D[first]],x=i-K+1,y=x+K-1;
	}
	
	ofstream fout(OUT);
	fout<<x+1<<" "<<y+1<<" "<<Max<<"\n";
	fout.close();
	
	return 0;
}