Cod sursa(job #431287)

Utilizator erzsikeRusz Elisabeta erzsike Data 31 martie 2010 20:32:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 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() 
{
	ifstream f("secventa.in");
	freopen("secventa.out","w",stdout);
	f>>n>>k; 
	for(i=1;i<=n;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; 
}