Mai intai trebuie sa te autentifici.

Cod sursa(job #302221)

Utilizator cotofanaCotofana Cristian cotofana Data 8 aprilie 2009 19:13:18
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <deque>
#define dim 500100

using namespace std;

int n, k, v[dim];
char s[dim*8], *p;
deque<int> d;

int main()
{
	int i, min=0, x=0, y=0;
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	scanf("%d %d\n", &n, &k);
	fgets(s, dim*8, stdin);
	p=s;
	for (i=1; i<=n; i++)
	{
		while (*p==' ') p++;
		
		if (*p=='-') min=1, p++;
		else min=0;
		
		v[i]=0;
		while (*p>='0' && *p<='9')
			v[i]=v[i]*10+*p-'0', p++;
		
		if (min) v[i]*=-1;
	}
	
	v[0]=-1<<30;
	for (i=1; i<=n; i++)
	{
		while (d.size() && v[i]<=v[d.back()]) d.pop_back();
		d.push_back(i);
		
		if (d.front()==i-k) d.pop_front();
		
		if (i>=k)
		{
			if (v[d.front()]>v[min])
			{
				min=d.front();
				x=i-k+1;
				y=i;
			}
		}
	}
	
	printf("%d %d %d\n", x, y, v[min]);
	return 0;
}