Cod sursa(job #815386)

Utilizator andreea29Iorga Andreea andreea29 Data 16 noiembrie 2012 21:49:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<cstring>
#define Nmax 500010
#define Nmax1 4000000
#define INFI 300010
using namespace std;
int n, k, a[Nmax], l, r, c[Nmax], dr, minim, p, x;
char s[Nmax1], d[5];
int main()
{
	ifstream f("secventa.in");
	ofstream h("secventa.out");
	
	f >> n >> k;
	f.getline(d, 5);
	f.getline(s, Nmax1);
	int ind = strlen(s) - 1;
	int j = 0;
	p = 0;
	while (j <= ind)
	{
		if (s[j] == '-')
		{
			x = 0;
			++j;
			while (s[j] >= '0' && s[j] <= '9')
			{
				x = x * 10 + int (s[j]) - 48;
				++j;
			}
			x = -x;
			a[++p] = x;
			
		}
		else
			if (s[j] >= '0' && s[j] <= '9')
			{
				x = 0;
				while (s[j] >= '0' && s[j] <= '9')
				{
					x = x * 10 + int (s[j]) - 48;
					++j;
				}
				x = x;
				a[++p] = x;
			}
		++j;
	}
//	for (int i = 1; i <= n; ++i)
//		f >> a[i];
	f.close();
	minim = - INFI;
	l = 1;
	r = 0;
	for (int i = 1; i <= n; ++i)
	{
		while (l <= r && a[i] <= a[c[r]])
			--r;
		c[++r] = i;
		if (i - k == c[l])
			++l;
		if (minim < a[c[l]] && i >= k)
		{
			minim = a[c[l]];
			dr = i;
		}
	}
	h << dr + 1 - k << " " << dr << " " << minim << '\n';
	h.close();
	return 0;
}