Cod sursa(job #407654)

Utilizator nandoLicker Nandor nando Data 2 martie 2010 15:33:30
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <deque>

using namespace std;

//<parsare>
FILE* fin=fopen("secventa.in","r");
const unsigned maxb=8192;
char buf[maxb];
unsigned ptr=maxb;

inline int getInt(){
	int nr=0,mul=1;
	while(buf[ptr]<'0'||'9'<buf[ptr]||buf[ptr]=='-'){
		if(buf[ptr]=='-'){
			mul=-1;
		}
		if(++ptr>=maxb)
			fread(buf,maxb,1,fin),ptr=0;
	}
	while('0'<=buf[ptr]&&buf[ptr]<='9'){
		nr=nr*10+buf[ptr]-'0';
		if(++ptr>=maxb)
			fread(buf,maxb,1,fin),ptr=0;
	}
	return nr*mul;
}
//</parsare>

int vec[510000];
deque<int>deq;

int main(){
	FILE* fout=fopen("secventa.out","w");
	int n=getInt(),k=getInt();
	for(int i=0;i<n;i++){
		vec[i]=getInt();
	}
	int end=0,max=-6000000;
	for(int i=0;i<n;i++){
		while(deq.size()>0&&deq.back()>vec[i]){
			deq.pop_back();
		}
		deq.push_back(vec[i]);
		if(i>=k){
			if(i>k){
				if(deq.front()==vec[i-k]){
					deq.pop_front();
				}
			}
			if(max<deq.front()){
				max=deq.front();
				end=i;
			}
		}
	}
	fprintf(fout,"%d %d %d\n",end-k+2,end+1,max);
	fclose(fin);
	fclose(fout);
	return 0;
}