Cod sursa(job #1780)

Utilizator astronomyAirinei Adrian astronomy Data 14 decembrie 2006 18:52:49
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>

#define MAXN (1 << 19)
#define min(a,b) ((a) < (b) ? (a) : (b))

int N, K;
int A[MAXN], Q[MAXN], poz[MAXN];
int best = - (1 << 30), pi, pf;

void solve(void)
{
	int i, inc = 1, sf = 1, baza;
	Q[1] = A[1], poz[1] = 1;
	for(i = 2; i <= K-1; i++)
	{
		while(A[i] <= Q[sf] && sf > 0) sf--;
		Q[++sf] = A[i], poz[sf] = i;
	}
	for(i = K; i <= N; i++)
	{
		while(i - poz[inc] >= K) inc++;
		baza = min(A[i], Q[inc]);
		if(baza > best) best = baza, pi = i-K+1, pf = i;
		while(A[i] <= Q[sf] && sf > 0) sf--;
		Q[++sf] = A[i], poz[sf] = i;
		if(inc > sf) inc = sf;
	}
}

void read_data(void)
{
	int i;
	scanf("%d %d\n", &N, &K);
	for(i = 1; i <= N; i++)
		scanf("%d ", &A[i]);
}

void write_data(void)
{
	printf("%d %d %d\n", pi, pf, best);
}

int main(void)
{
	freopen("secventa.in", "rt", stdin);
	freopen("secventa.out", "wt", stdout);

	read_data();
	solve();
	write_data();

    return 0;
}