Cod sursa(job #288354)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 25 martie 2009 18:57:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda aa Marime 1.16 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;   
}