Cod sursa(job #565870)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2011 13:09:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;
#define dim 500001
int v[dim], deque[dim];
int main()
{
	ifstream fin("secventa.in");
	ofstream fout("secventa.out");
	int n, i, k;
	fin>>n >>k;
	
	for(i=1;i<=n;++i)
		fin>>v[i];
	
	for(i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(v[i]<v[j])
			{
			int	aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
	
	//sort(v+1,v+n+1);
	
		int	ls=1,ld=0;
			
		for(i=1;i<k;++i)
		{
			while(ls<=ld && v[i]<=v[deque[ld]])
				--ld;
			deque[++ld]=i;
		}
		
		int minim=-30001, st;
		
		for(i=k;i<=n;++i)
		{
			while(ls<=ld && v[i]<=v[deque[ld]])
				--ld;
			deque[++ld]=i;
			
			while(ls<=ld && deque[ls]<i-k+1)
				++ls;
			
			if(v[deque[ls]]>minim)
			{
				minim=v[deque[ls]];
				st=i;
			}
		}
		
		fout<<st-k+1 <<" " <<st <<" " <<minim;
		
		
			
			
	return 0;
}