Cod sursa(job #815334)

Utilizator andreea29Iorga Andreea andreea29 Data 16 noiembrie 2012 21:04:20
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
#define Nmax 500010
#define INFI 30010
using namespace std;
int n, k, a[Nmax], l, r, c[Nmax], st, dr, minim;
int main()
{
	ifstream f("secventa.in");
	ofstream h("secventa.out");
	f >> n >> k;
	for (int i = 1; i <= n; ++i)
		f >> a[i];
	f.close();
	minim = - INFI;
	l = r = 1;
	c[r] = 1;
	for (int i = 2; i < k; ++i)
	{
		if (l <= r && a[i] <= a[c[r]])
			r--;
		r++;
		c[r] = i;
	}
	for (int i = k; i <= n; ++i)
	{
		if (l <= r && a[i] <= a[c[r]])
			r--;
		r++;
		c[r] = i;
		if (minim < a[c[l]])
		{
			minim = a[c[l]];
			st = i + 1 - k;
			dr = i;
		}
		if (c[l] <= i + 1 -k)
			l++;
	}
	h << st << " " << dr << " " << minim << '\n';
	h.close();
	return 0;
}