Cod sursa(job #1779)

Utilizator astronomyAirinei Adrian astronomy Data 14 decembrie 2006 18:50:36
Problema Secventa Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>

#define MAXN 500003
#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, &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;
}