Cod sursa(job #74577)

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


int a[500000], d[500000], dv[500000];

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

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

void citire(){
	freopen("secventa.in", "r", stdin);
    scanf("%ld %ld", &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 (long i = 1; i < n ; i++) {
		while (p <= u && d[p] <= i - k) p++;
		while (p <= u && dv[u] >= a[i]) u--;
		add_deque(i);
		if (i < k - 1)
			continue;
		if (dv[p] > vmin ){
			vmin = dv[p];
			pi = i - k + 1;
		//	ps = i;
		}	
	}
}

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

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