Cod sursa(job #1051868)

Utilizator apopeid15Apopei Daniel apopeid15 Data 10 decembrie 2013 17:24:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
# include <stdio.h>
# include <limits>
# define NMax 500001
using namespace std;
 
FILE *fin,*fout;
 
int n,k , Max ,st,dr;
short v[NMax];
int deck[NMax]; // deque
 
short Numar()
{
    char x;
    short t = 0 , y = 1;
    x = getc(fin);
    while( x == ' ' || x == '\n' || x == '-' )
    {
        if( x == '-' )
            y *= -1;
        x = getc(fin);
    }
    while( x >= '0' && x <= '9' )
    {
        t = t*10 + x-'0';
        x = getc(fin);
    }
    return t*y;
}
 
void Citire()
{
    fin = fopen("secventa.in","r");
    fscanf(fin,"%d%d",&n,&k);
    for( int i = 1 ; i <= n ; ++i )
        v[i] = Numar();
    fclose(fin);
}
 
void Rezolv()
{
    int ultim , prim , i;
    Max = numeric_limits<int>::min();
    ultim = 1;
    prim = 0;
    for( i = 1 ; i <= n ; ++i )
    {
        while( prim <= ultim && v[i] <= v[deck[ultim]] )
            --ultim;
        deck[++ultim] = i;
        if( deck[prim] == i-k )
            ++prim;
        if( v[deck[prim]] > Max && i >= k )
        {
            Max = v[deck[prim]];
            st = i-k+1;
            dr = i;
        }
    }
}
 
inline void Tipar()
{
    fout = fopen("secventa.out","w");
    fprintf(fout,"%d %d %d",st,dr,Max);
    fclose(fout);
}
 
int main()
{
    Citire();
    Rezolv();
    Tipar();
    return 0;
}