Cod sursa(job #300687)

Utilizator alisssiaMititelu Andra alisssia Data 7 aprilie 2009 16:56:43
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
using namespace std;
#include<stdio.h>
#include<deque>
#define nmax 500001
#define inf 0x3f3f3f3f
deque<int>Q;
int v[nmax];
int n,k,maxim,in;

void push(int p)
{
	while(!Q.empty() && v[Q.back()]>v[p]) Q.pop_back();
	Q.push_back(p);
}

void read()
{
	freopen("secventa.in","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	scanf("%d",&v[i]);
}


int main()
{
	int i;
	maxim=-inf;
	read();
	for(i=0;i<n;i++)
	{
		push(i);
		while(i-Q.front()+1>k) Q.pop_front();
		if(maxim<v[Q.front()] && i>=k)
		{
			in=i-k+1;
			maxim=v[Q.front()];
		} 
		
	}
	
	freopen("secventa.out","w",stdout);
	printf("%d %d %d",in+1,in+k,maxim);
	return 0;
}