Cod sursa(job #1639807)

Utilizator bob123bobelus bob bob123 Data 8 martie 2016 14:05:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");
char s[2000006];
int ok,t,in,sf,nr,j,Max,Front,Back,n,k,i,a[500001],dq[500001];
int get()
{
    int x=0;ok=0;
    if(s[t]=='-') ok=1;
    while(s[t]!=' '&&s[t]!='\n')
            x=x*10+s[t]-'0',++t;
    if(ok==1)
        x=x*-1;
    ++t;
    return x;
}
int main()
{
    f>>n>>k;
    Front=1;Back=0;
    f.getline(s,4);
    f.getline(s,2000003);
    t=0;
    for(i=1;i<=n;++i)
        a[i]=get();
    Max=-10000000;
    for(i=1;i<=n;++i){
        while(Front<=Back&&a[i]<a[dq[Back]])
            --Back;
        dq[++Back]=i;
        if(dq[Front]==i-k)
            ++Front;
        if(a[dq[Front]]>Max&&i>=k)
            {
                Max=a[dq[Front]];
                in=i-k+1;
                sf=i;
            }
    }
    g<<in<<" "<<sf<<" "<<Max;
    return 0;
}