Cod sursa(job #464543)

Utilizator andunhillMacarescu Sebastian andunhill Data 20 iunie 2010 17:15:04
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream f("secventa.in") ; ofstream g("secventa.out");
struct numere
{	int val,begin,end;
}v[500001],max1;
int i,n,k;
deque<numere>vmin;
int main()
{	f>>n>>k;
	max1.val=-31000;
	for(i=1;i<=n;i++)
		f>>v[i].val , v[i].begin=i;
	for(i=1;i<=n;i++)
	{	while(!vmin.empty() && vmin.back().val>v[i].val )
			vmin.pop_back();
		vmin.push_back(v[i]);
		if(i-vmin.front().begin+1 > k )
			vmin.pop_front();
		if(max1.val<vmin.front().val)
		{	vmin.front().end=i , vmin.front().begin=i-k+1;
			max1=vmin.front();
		}
	}
	g<<max1.begin<<" "<<max1.end<<" "<<max1.val;
	f.close();
	g.close();
	return 0;
}