Cod sursa(job #370498)

Utilizator undogSavu Victor Gabriel undog Data 1 decembrie 2009 14:17:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <cstdio>

int v[500000];
int s[500000];

int main(){
	freopen("secventa.out","wt",stdout);
	
	int i,n,k;
	int st,sf,max=-1000000;
	
	
	int front=1,back=0;
	
	std::ifstream f("secventa.in");
	
	f>>n>>k;
	for(i=1;i<=n;i++)
		f>>v[i];
	
	for(i=1;i<=n;i++){
   		while( front<=back && v[i]<v[s[back]])back--;
    		s[++back]=i;
    		if(i>=k){
    			if(v[s[front]]>max){
        			max=v[s[front]];
        			st=i-k+1;
        			sf=k;
        		}
        	}
    		if(i-s[front]+1==k)front++;
    	}
	
	printf("%d %d %d",st,sf+st-1,max);
	
	return 0;
}