Cod sursa(job #1512827)

Utilizator daneelHolteiu Daniel daneel Data 28 octombrie 2015 18:18:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int minim(int a[],int s,int d)
{
    int i,min1;
    min1=a[s];
    for(i=s+1;i<=d;i++)
        if(a[i]<min1) min1=a[i];
    return min1;
}

void parsare(char s[],int a[])
{
    int i,k=1,p=0,nr;
    for(i=0;s[i];i++)
    {
        if(isdigit(s[i]) || s[i]=='-')
        {
            p++;
            k=1;
            nr=0;
            if(s[i]=='-')
            {
                k=-1;
                i++;
            }
            for(;isdigit(s[i]);i++)
            {
                nr=nr*10+s[i]-'0';
            }
        }
    a[p]=nr*k;
    }
    return;
}

int n,k,a[500001],i,s,d,min1,min2,p1,p2,front,back,deque[500001];
char sir[4000000];

int main()
{
    //int n,k,a[500001],i,s,d,min1,min2,p1,p2,front,back,deque[500001];

    in>>n;
    in>>k;

    in.getline(sir,4000000,EOF);
    parsare(sir,a);

    /*for(i=1;i<=n;i++) in>>a[i];*/
    //for(i=1;i<=n;i++) out<<a[i]<<" ";
    out<<"\n";
    s=d=1;
    min1=-30001;
    front=1;
    back=0;

    for(i=1;i<=n;i++)
    {
        if(i-deque[front]+1>k) front++;
        while(front<=back && a[i]<a[deque[back]]) back--;
        back++;
        deque[back]=i;
        min2=a[deque[front]];

        if(d-s+1!=k) d++;
            else{
                if(min2>min1)
                {
                    p1=s;
                    p2=d;
                    min1=min2;
                    s++;
                    d++;
                }else{
                    s++;
                    d++;
                }
            }
    }

    out<<p1<<" "<<p2<<" "<<min1;

    in.close();
    out.close();
    return 0;
}