Cod sursa(job #755129)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 4 iunie 2012 18:45:29
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
#include<cstdlib>

using namespace std;

int a[500010], q[500010];
char *buffer;

void read(int &x)
{
	while((*buffer < '0') || (*buffer > '9'))
		++buffer;
	
	x = 0;
	
	while((*buffer >= '0') && (*buffer <= '9')){
		x = ((x * 10) + (*buffer - '0'));
		++buffer;
	}
}

int main()
{	
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	int N, k, i, st, dr, rez, poz, fs;
	
	fseek(stdin, 0, SEEK_END);
	fs = ftell(stdin);
	buffer = (char*) malloc(fs);
	rewind(stdin);
	fread(buffer, 1, fs, stdin);
	
	read(N), read(k);
	
	for(i = 1; i <= N; ++i)
		read(a[i]);
	
	rez = -30010;
	st = 1, dr = 0;
	
	for(i = 1; i <= N; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ]))
			dr--;
		q[ ++dr ] = i;
		
		if(q[st] + k == i)
			st++;
		
		if(i >= k)
			if(a[ q[st] ] > rez)
				rez = a[ q[st] ], poz = i;
	}
	
	printf("%d %d %d", poz - k + 1, poz, rez);
	
	return 0;
}