Cod sursa(job #372416)

Utilizator GotenAmza Catalin Goten Data 9 decembrie 2009 21:42:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream>
#include<iostream>

using namespace std;

long i,n,a[5000002],s,d,k,c[5000002],pozmin,pozmax,cds,m;

int main()
{
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f>>n>>k;
	for(i=1;i<=n;i++)
		f>>a[i];
	s=1;d=1;
	c[d]=1;
	for(i=2;i<k;i++)
	{
		while(a[i]<=a[c[d]]&&d>=s)d--;
		c[++d]=i;
	}
	m=a[c[s]];
	pozmax=k;
	pozmin=1;
	for(i=k;i<=n;i++)
	{
		cds=c[s];
		while(c[s]+k<=i)s++;
		while(a[i]<=a[c[d]]&&d>=s)d--;
		c[++d]=i;
		if(cds!=c[s])
			if(a[c[s]]>m)
			{
				m=a[c[s]];
				pozmax=i;
				pozmin=i-k+1;
			}			
	}
	g<<pozmin<<' '<<pozmax<<' '<<m;
	return 0;
}