Cod sursa(job #828759)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 4 decembrie 2012 13:07:54
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
 
using namespace std;
 
ifstream in("secventa.in");
ofstream out("secventa.out");
 
int n,k,i,dq[1<<19];
short int v[1<<19];
int st=1,dr=0,s,d;
int maxx=-1<<15;
  
int main(){
    in>>n>>k;
    st=1; dr=0;
    for(i=1;i<=n;i++){
        in>>v[i];
    }
    for(i=1;i<k;i++){
        while(st<=dr&&v[dq[dr]]>=v[i]){
			--dr;
		}
		dq[++dr]=i;
    }
    for(i=k;i<=n;i++){
        if(i-k==dq[st]){
			++st;
		};
        while(st<=dr&&v[dq[dr]]>=v[i]){
			--dr;
		}
		dq[++dr]=i;
        if(v[dq[st]]>maxx){
            maxx=v[dq[st]];
            d=i;
            s=i-k+1;
        }
    }
    out<<s<<" "<<d<<" "<<maxx;
    return 0;
}