Cod sursa(job #718738)

Utilizator ColcerPColcer Paul ColcerP Data 21 martie 2012 05:16:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <deque>
using namespace std;

#define infile "secventa.in"
#define outfile "secventa.out"
#define NMAX 500005

FILE *fin,*fout;
int n,k;
int x[NMAX];
int baza=-35000,start=-1;
char sir[NMAX*10];
deque <int> coada;

void citire()
  {
   int j=0,semn;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d\n",&n,&k);
   fgets(sir,sizeof(sir),fin);
   for(int i=0;i<n;i++)
      {
       semn=0;
       x[i]=0;
       while(sir[j]!='-' && (sir[j]<'0' || sir[j]>'9'))
            j++;
       if(sir[j]=='-')
         {
          semn=1;
          j++;
         }
       while(sir[j]>='0' && sir[j]<='9')
            {
             x[i]=x[i]*10+(sir[j]-'0');
             j++;
            }
       if(semn)
         x[i]=-x[i];
      }
   fclose(fin);
  }

void scriere()
  {
   fout=fopen(outfile,"w");
   fprintf(fout,"%d %d %d\n",start+1,start+k,baza);
   fclose(fout);
  }

void solve()
  {
   int i;
   for(i=0;i<k;i++)
      {
       while(!coada.empty() && x[coada.back()]>=x[i])
            coada.pop_back();
       coada.push_back(i);
      }
   baza=x[coada.front()];
   start=0;
   for(i=k;i<n;i++)
      {
       if(coada.front()==i-k)
         coada.pop_front();
       while(!coada.empty() && x[coada.back()]>=x[i])
            coada.pop_back();
       coada.push_back(i);
       if(baza<x[coada.front()])
         {
          baza=x[coada.front()];
          start=i-k+1;
         }
      }
  }


int main()
{
citire();
solve();
scriere();
return 0;
}