Cod sursa(job #443590)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 17 aprilie 2010 17:40:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#define max_N 500005
#define INITMAX -320000
#define max_V N*8

using namespace std;

int Values[max_N], i, j, K, N, First, Last, x, y, maxim, Deque[max_N];
char Sir[max_N * 7];

void Parse()
{
	int semn = 0;
	fgets(Sir, max_N * 7, stdin);
	for(i = 1; i <= N; i ++)
	{	
		semn = 0;
		while(Sir[j] == ' ') j ++;
		if(Sir[j] == '-')
			semn = 1, j ++;
		while('0' <= Sir[j] && Sir[j] <= '9')
			Values[i] = Values[i] * 10 + (Sir[j ++] - '0');
		if(semn == 1)
			Values[i] = Values[i] * (-1);
	}
}



int main()
{	
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d %d\n", &N, &K);
	maxim = INITMAX;
	Parse();
	/*for(i = 1; i <= N; i ++)
		scanf("%d", &Values[i]);*/
	
	First = 1, Last = 0;
	for(i = 1; i <= N; i ++)
	{
		while(First <= Last && Values[i] <= Values[Deque[Last]]) Last --;
		Deque[++Last] = i;
		if(Deque[First] == i - K)
			First ++;
		if(i >= K)
			if(Values[Deque[First]] > maxim)
			{
				maxim = Values[Deque[First]];
				x = i - K + 1;
				y = i;
			}
	}
	
	printf("%d ", x);
	printf("%d ", y);
	printf("%d", maxim);
	return 0;
}