Cod sursa(job #565873)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2011 13:13:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 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];

		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;
}