Cod sursa(job #1507668)

Utilizator MarghescuGabriel Marghescu Marghescu Data 21 octombrie 2015 19:55:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <climits>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n,k,i,deq[5000000],a[5000000],p1,p2,minim=-INT_MAX;
char s[5000000];
int main()
{
    f>>n>>k;
    f.getline(s,5000000,EOF);
    int semn,p=0;
    for(i=0; s[i]; i++)
    {
        semn=1;
        if(s[i]=='-')
            {semn=-1;
            i++;
            }
        if(isdigit(s[i]))
        {
            ++p;
            for(;isdigit(s[i]);i++)
                a[p]=a[p]*10+s[i]-'0';
             a[p]*=semn;
        }
    }

    int prim=1,ultim=0;
    for(i=1; i<=n; i++)
    {
        while(a[i]<=a[deq[ultim]] && prim<=ultim)
            ultim--;
        ultim++;
        deq[ultim]=i;

        if(deq[prim]<=i-k)
            prim++;
        if(i>=k)
        {
            if(a[deq[prim]]>minim)
            {
                minim=a[deq[prim]];
                p1=i-k+1;
                p2=i;
            }
            else
                if(deq[prim]==minim && prim<p1)
                {
                    p1=i-k+1;
                    p2=i;
                }
        }
    }
    g<<p1<<' '<<p2<<' '<<minim;
    return 0;
}