Cod sursa(job #499412)

Utilizator buburuzaLaura S buburuza Data 9 noiembrie 2010 19:04:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <deque>

using namespace std;

const char InFile[]="secventa.in";
const char OutFile[]="secventa.out";

ifstream fin(InFile);
ofstream fout(OutFile);

struct s
{
	s(int x2=0,int pos2=0):x(x2),pos(pos2){}
	int x,pos;
};

int x,n,k,st,sf,sol=-50000,solst,solsf;
deque<s> d;

void add(int x, int i)
{
	while(!d.empty())
	{
		if(d.back().x<x)
		{
			break;
		}
		d.pop_back();
	}
	d.push_back(s(x,i));
	sf=i;
}

void update()
{
	if(sol<d.front().x)
	{
		sol=d.front().x;
		solst=st;
		solsf=sf;
	}
}

int main()
{
	fin>>n>>k;
	st=1;
	for(register int i=1;i<=n;++i)
	{
		fin>>x;
		add(x,i);
		if(sf-st+1>=k)
		{
			while(sf-d.front().pos>=k)
			{
				st=d.front().pos+1;
				d.pop_front();
			}
			update();
		}
	}
	fin.close();

	fout<<solst<<" "<<solsf<<" "<<sol;
	fout.close();
	return 0;
}