Cod sursa(job #414964)

Utilizator al_flAlexandru Flavian al_fl Data 10 martie 2010 19:24:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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;
}