Cod sursa(job #424844)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 25 martie 2010 11:32:56
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<fstream>
#define Nmax 500010
#define Inf 1<<30
using namespace std;
int v[Nmax],d[Nmax],p,u,i,k,baza,st,dr,n;

int main()
{
	//freopen("secventa.in","r",stdin);
	ifstream f("secventa.in");
	freopen("secventa.out","w",stdout);
	
	//scanf("%d %d",&n,&k);
	f>>n>>k;
	
	for(i=1;i<=n;i++)
		//canf("%d",&v[i]);
		f>>v[i];
	
	baza=-Inf;
	for(p=u=i=1;i<=n;i++)
	{
		while( d[p] <= i-k && p<=u ) p++;
		while( v[d[u]]>v[i] && p<=u) u--;
		
		d[++u]=i;
		
		if(i>=k) 
			if(v[d[p]]>baza) 
			{
				baza=v[d[p]];
				dr=i;
				st=i-k+1;
			}
	}
	
	printf("%d %d %d",st,dr,baza);
	
	return 0;
}