Cod sursa(job #74605)

Utilizator zobicaMarin Marin zobica Data 26 iulie 2007 18:04:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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("%ld %ld", &n, &k);
//    for (int i = 0; i < n; i++)
//		scanf("%d", &a[i]);
//    fclose(stdin);
//}


void citire(){
	freopen("secventa.in", "r", stdin);
	scanf("%ld %ld\n", &n, &k);
	long i = 0;
	int x = 0;
	char c = getc(stdin);
	int semn = 1;
	while (!feof(stdin)) {
		if (c == '-') {
			semn = -1; 
			c = getc(stdin);
			continue;
		}
		if (c >= '0' && c <= '9')
			x = x * 10 + c - '0';
		else {
			a[i++] = semn * x;
			semn = 1;
			x = 0;
		}
		c = getc(stdin);
	}
	a[i++] = x * semn;

	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 && a[d[u]] >= a[i]) u--;
		while (p <= u && d[p] <= i - k) p++;

		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("%ld %ld %ld", pi + 1, pi + k, vmin);
	fclose(stdout);
}

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