Cod sursa(job #74604)

Utilizator zobicaMarin Marin zobica Data 26 iulie 2007 17:56:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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;
	while(i < n) {
		char s[1024];
		fgets(s, 1024, stdin);
		int x = 0;
		int semn = 1;
		for (long j = 0;  s[j]!='\n'; j++) {
			if (s[j] == '-') {
				semn = -1; 
				continue;
			}

			if (s[j] >= '0' && s[j] <= '9')
				x = x * 10 + s[j] - '0';
			else {
				a[i++] = semn * x;
				semn = 1;
				x = 0;
			}
		}
		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;
}