Cod sursa(job #74573)

Utilizator zobicaMarin Marin zobica Data 26 iulie 2007 12:52:30
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>


int a[500000], d[500000];

long k, n, p = 0, u = -1, pi = 1, ps = 1, vmin;

void add_deque(int poz) {	
	d[++u] = poz;
}

void citire(){
	freopen("secventa.in", "r", stdin);
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
    fclose(stdin);
}

void rezolva() {
	add_deque(0);
	if (k == 1)
		vmin = a[0];
	else
		vmin = -32767;
	for (int i = 1; i < n ; i++) {
		while (p <= u && d[p] <= i - k) p++;
		while (p <= u && a[d[u]] >= a[i]) u--;
		add_deque(i);
		if (i < k - 1)
			continue;
		if (a[d[p]] > vmin ){
			vmin = a[d[p]];
			pi = i - k + 1;
			ps = i;
		}	
	}
}

void scrie(){
	freopen("secventa.out", "w", stdout);
	printf("%d %d %d", pi + 1, ps + 1, vmin);
	fclose(stdout);
}

int main() {
	citire();
	rezolva();
	scrie();
	return 0;
}