Cod sursa(job #807510)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 4 noiembrie 2012 20:50:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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 get_number(int &ind, int dim) {
	
	char minus = 0;
	int nr = 0;
	
	if(buff[ind] == '-') {
		++ind;
		minus = 1;
	}
	while(buff[ind]>='0' && buff[ind]<='9' && ind<dim) {
		nr = nr*10 + buff[ind]-'0';
		++ind;
	}
	++ind;
	
	return !minus ? nr : -nr;
}

int main() {
	
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	
	int i, ind, dim;
	
	scanf("%d %d\n",&N,&k);
	
	dr = 0;
	st = 1;
	minim = -1<<30;
	
	gets(buff);
	ind = 0;
	dim = strlen(buff);
	
	for(i=1; i<=N; ++i) {
		
		V[i] = get_number(ind, dim);
		
		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[dr] - Deque[st] >= k)
			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;
}