Cod sursa(job #299151)

Utilizator alisssiaMititelu Andra alisssia Data 6 aprilie 2009 16:41:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 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);
}

long  min(long  i)
{
	while(i-Q.front()+1>k) Q.pop_front();
	return Q.front();
}

void read()
{
	freopen("deque.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()])
		{
			in=Q.front();
			maxim=v[Q.front()];
		}
	}
	freopen("deque.out","w",stdout);
	printf("%d %d %d",in+1,in+k,maxim);
	return 0;
}