Cod sursa(job #807503)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 4 noiembrie 2012 20:38:31
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<string.h>

#define Nmax 500001

int V[Nmax], Deque[Nmax], N, k, st, dr, poz, minim;
char buff[Nmax*15];

int main() {
	
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	
	int i, nr, dim;
	char minus;
	
	scanf("%d %d\n",&N,&k);
	
	fgets(buff,Nmax*15,stdin);
	dim = strlen(buff);
	i = 0;
	nr = 0;
	minus = 0;
	while(i<dim) {
		if(buff[i] == '-') {
			minus = 1;
			++i;
			continue;
		}
		if(buff[i]>='0' && buff[i]<='9') {
			while(buff[i]>='0' && buff[i]<='9' && i<dim) {
				nr = nr*10 + buff[i]-'0';
				++i;
			}
			if(minus) { 
				nr = -nr;
				minus = 0;
			}
			V[++V[0]] = nr;
			nr = 0;
			continue;
		}
		if(buff[i]==' ') {
			++i;
			continue;
		}
	}
	
	st = dr = 1;
	Deque[st] = 1;
	minim = -1<<30;
	
	for(i=2; i<=N; i++) {
		
		while(V[i] <= V[Deque[dr]] && st<=dr)
			dr--;
		// sterg din deque toate elem mai mari ca V[i] formand mereu in felul asta un sir crescator in deque
		
		Deque[++dr] = i;
		// adaug pozitia elementului curent
		
		while(Deque[st]+k <= i)
			st++;
		
		if(minim < V[Deque[st]] && i>=k) {
			minim = V[Deque[st]];
			poz = i;
		}
	}
	
	printf("%d %d %d\n",poz-k+1,poz,minim);
	
	return 0;
}