Cod sursa(job #868987)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 31 ianuarie 2013 20:38:39
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<fstream>
#include<deque>
using namespace std;

short int a[500001],mx;
deque <short int> c;
int n,k,u,p,i,x;

int main()
{
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f >> n >> k;
	for (i=1;i<=n;i++)
		f >> a[i];
	p=1;u=0;mx=-30001;
	for (i=1;i<k;i++)
	{
		while ((!c.empty()) && (a[i]<c.back()))
			c.pop_back();
		c.push_back(a[i]);
	}
	for (i=k;i<=n;i++)
	{
		while ((!c.empty()) && (a[i]<c.back()))
			c.pop_back();
		c.push_back(a[i]);
		if (i>=k)
		{
			if ((i>k) && (a[i-k]==c.front()))
				c.pop_front();
			if (c.front()>mx)
			{
				mx=c.front();
				x=i;
			}
		}
	}
	g << x-k+1 << ' ' << x << ' ' << mx;
	return 0;
}