Cod sursa(job #398375)

Utilizator deiosxHalalai Tudor Andrei deiosx Data 18 februarie 2010 16:31:43
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
using namespace std;
const int N = 1<<23;
int st=0, dr=-1, n, k, dq[N], v[N], mx=-1<<15, stm, drm;
ifstream in("secventa.in");
ofstream out("secventa.out");
inline void stanga(int i)
{
	if(i - dq[st] == k)
		++st;
}
inline void dreapta(int i)
{
	while(st <= dr && v[i] <= v[dq[dr]])
		--dr;
	dq[++dr] = i;
}
void citire()
{
	int i;
	in>>n;
	in>>k;
	for(i=0; i<n; i++)
		in>>v[i];
}
int main()
{
	int i;
	citire();
	for(i=0; i<k-1; i++)
		dreapta(i);
	for(; i<n; i++)
	{
		dreapta(i);
		stanga(i);
		if(v[dq[st]] > mx)
		{
			drm = i;
			stm = i-k+1;
			mx = v[dq[st]];
		}
	}
	out<<stm+1<<' '<<drm+1<<' '<<mx;
	return 0;
}