Cod sursa(job #1050330)

Utilizator ShaDoWsiD100Rzv Rzv ShaDoWsiD100 Data 8 decembrie 2013 15:03:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#define DIM 10000
using namespace std;
FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
int n,v[500001],deque[500001],i,front,back,k,Max=-999999,start,finish;
char buff[DIM];
int poz=0;

void citeste(int &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,f),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,f),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}
int main()
{
    fscanf(f,"%d%d",&n,&k);
    for(i=1;i<=n;i++)
        citeste(v[i]);
    front=1;
    back=0;
    for(i=1;i<=n;i++)
    {
        while(front<=back && v[i]<=v[deque[back]])
            back--;
        deque[++back]=i;
        if(deque[front]==i-k)
            front++;
        if(v[deque[front]]>Max && i>=k){
            Max=v[deque[front]];
            start=i-k+1;
            finish=i;
        }
    }
    fprintf(g,"%d %d %d",start,finish,Max);
    return 0;
}