Cod sursa(job #2120516)

Utilizator tiberiu392Tiberiu Ungurianu tiberiu392 Data 2 februarie 2018 16:04:01
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int n , k , j , inc ,maxim,poz,fin,b[500005],a[500005],i,semn;
char s[10000005];
int main()
{
    f>>n>>k;
    f.get();
    f.get(s,10000005);
    for( i = 1 ;i <= n ; i++ )
    {
        semn = 1;
        if(s[j] == ' ')
            j++;
        if(s[j] == '-')
        {
            semn = -1;
            j++;
        }
        while('0' <= s[j] && s[j] <= '9')
        {
            a[i] = a[i]*10+s[j]-'0';
            j++;
        }
        a[i]*= semn;
    }
    maxim = -300001;
    inc = 1;
    for( i = 1 ; i <= n ;i++)
    {
        while( inc <= fin && a[i] < a[b[fin]])
        {
            fin--;
        }
        fin++;
        b[fin] = i;
        if( b[inc] <= i-k)
            inc++;
        if( i >= k && a[b[inc]] > maxim)
        {
            maxim = a[b[inc]];
            poz = i;
        }
    }
    g << poz-k+1 << " " << poz << " " << maxim;
    return 0;
}