Cod sursa(job #632464)

Utilizator floringh06Florin Ghesu floringh06 Data 11 noiembrie 2011 10:48:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <string.h>

using namespace std;

#define MAX_N 500005
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define LIM 3300000
#define INF 35000

short int A[MAX_N]; 
int Deq[MAX_N];
int li=1,lf,N,i,K;
int BEST = -INF;
int In, Out;
char sir[LIM];

    void readdata()
    {
     int x,ind,i=0,sem=1;    
     fgets(sir, LIM, stdin); x = ind = 0;
     int L=strlen(sir);
     for (ind=0; ind<=L; ++ind)
      {
         if (sir[ind]==' ' || sir[ind]=='\n') 
           {
             if (sem==1) A[++i]=x; else A[++i]=-x;
             sem=1; 
             x=0;
           }       
         if (sir[ind]=='-') sem=-1;
         if (sir[ind]>='0' && sir[ind]<='9')
           x = x*10+(sir[ind]-'0');
      }     
    }     


    void Deqin (int x)
    {
         Deq[++lf]=x;
         if (A[x]<A[Deq[li]]) {  Deq[li]=x; lf=li; }  
         while (A[Deq[lf]]<A[Deq[lf-1]] && lf>li) 
          { Deq[lf-1]=Deq[lf]; lf--; }
         while (x-Deq[li]>=K) ++li;
    }      
    
    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        scanf ("%d %d\n" , &N, &K);
        
        readdata();
    
        for (i=1; i<=N; ++i)
         {         
          Deqin(i);
          if (A[Deq[li]]>BEST && i>K-1) 
           {
             BEST=A[Deq[li]]; In=i-K+1; Out=i;
           }
         }   
         
        printf("%d %d %d\n",In, Out, BEST);   
        return 0;
    }