Cod sursa(job #287577)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 24 martie 2009 23:02:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<fstream>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");
/*

FILE *fin=fopen("secventa.in","r"),
    *fout=fopen("secventa.out","w");
*/
int N,A[500005],dq[500005],li,lf,K;

int main(){
  //  fscanf(fin,"%d %d",&N,&K);
    fin>>N>>K;
    int pozi,pozf,min;
    li=1,lf=0;
    for(int i=1;i<=K;i++){
        //fscanf(fin,"%d",&A[i]);
        fin>>A[i];
        while( lf>=li && A[i]<A[dq[lf]] )
            --lf;
        dq[++lf]=i;

    }

    pozi=1,pozf=K,min=A[dq[1]];

    for(int i=K+1;i<=N;i++){
        //fscanf(fin,"%d",&A[i]);
        fin>>A[i];
        if(i-dq[li]==K)
            ++li;
        while( lf>=li && A[i]<A[dq[lf]])
            --lf;
        dq[++lf]=i;

        if(A[dq[li]]>min)
            pozi=i-K+1,pozf=i,min=A[dq[li]];
    }

    fout<<pozi<<" "<<pozf<<" "<<min<<"\n";
    fin.close();
    fout.close();
    //fprintf(fout,"%d %d %d\n",pozi,pozf,min);
   // fclose(fin);
   // fclose(fout);
    return 0;
}