Cod sursa(job #522936)

Utilizator elfusFlorin Chirica elfus Data 16 ianuarie 2011 18:27:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
/*Sfat pentru cine face problema cu deque si are TLE : folositi fstream si inlocuiti scanfurile si printfurile.
Mai mult de 90 (oricat de optim ar fi algoritmu) nu am putut sa scot cu stdio. Buna treaba cu imbunatatirea testelor, pacat ca s-a lucrat
numai in trecut */

#include<fstream>
#define LMAX 500100

int n,k;
int x[LMAX],q[LMAX];

using namespace std;

void read()
{
int i;
ifstream fin("secventa.in");
fin>>n>>k;
for(i=1;i<=n;i++)
	fin>>x[i];
}

void solve()
{
ofstream fout("secventa.out");
int p=1,u=0,i,poz,max=poz=-(1<<25);
for(i=1;i<=n;i++)
	{
	while(p<=u && x[i]<=x[q[u]])
		u--;
	q[++u]=i;
	if(q[p]+k==i)
		p++;
	if(i>=k)
		if(x[q[p]]>max)
			max=x[q[p]],poz=i;
	}
fout<<poz-k+1<<" "<<poz<<" "<<max;
}

int main()
{
read();
solve();
return 0;
}