Cod sursa(job #580706)

Utilizator shnakoVlad Schnakovszki shnako Data 13 aprilie 2011 13:34:04
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <deque>
#define LIM 500005
using namespace std;
FILE *f=fopen("secventa.in", "r"), *g=fopen("secventa.out", "w");
int i, n, k, maxx, start, end, s[LIM];
deque <int> v;

inline void citeste()
{
	fscanf(f, "%d%d", &n, &k);
	for (i=1;i<=n;i++)
		fscanf(f, "%d", &s[i]);
}

inline void deckuieste()
{
	maxx=-30005;
	for(i=1;i<=k;i++)
	{
		while(!v.empty()&&s[v.back()]>=s[i])
			v.pop_back();
		v.push_back(i);
	}
	for (i=k;i<=n+1;i++)
	{
		if(s[v.front()]>maxx)
		{
			maxx=s[v.front()];
			start=i-k;
			end=i-1;
		}
		while(!v.empty()&&s[v.back()]>=s[i])
			v.pop_back();
		v.push_back(i);
		if (v.front()<=i-k)
			v.pop_front();
	}
}

inline void tipareste()
{
	fprintf(g, "%d %d %d", start, end, maxx);
}

int main()
{
	citeste();
	deckuieste();
	tipareste();
	fclose(f);
	fclose(g);
	return 0;
}