Cod sursa(job #1506489)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 20 octombrie 2015 18:56:33
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;
ifstream fi ("secventa.in");
ofstream fo ("secventa.out");
int a[500008],b[500008],l[500008],s,d,i,k,n,sol,p1,p2,lsn,semn,v,j;
string sn;
int main()
{
    fi>>n>>k;
    fi.get();
    //for (i=1; i<=n; i++) fi>>a[i];
    getline(fi, sn);
    sn = sn + ' ';
    lsn = sn.size();
    semn = 1;
    v = 0;
    for (j = 0; j < lsn; j++)
    {
        if ('0' <= sn[j] and sn[j] <= '9')
            v = v * 10 + sn[j] - '0';
        else if (sn[j] == '-')
            semn = -1;
        else
            a[++i] = v*semn, v = 0, semn = 1;
    }
    d=1;
    s=1;
    sol=-56585;
    b[1] = a[1];
    l[s] = 1;
    for (i=2; i<=n; i++)
    {
        while (a[i]<=b[d] and s<=d)
            d--;
        d++;
        b[d]=a[i];
        l[d]=i;
        if (i - l[s] == k) s++;
        if (k <= i)
            if (b[s]>sol)
            {
                sol=max (b[s],sol);
                p1=i-k+1;
                p2=i;
            }
    }
    fo<<p1<<' '<<p2<<' '<<sol;
    return 0;
}



//k = 3
//-1 2 3 1 0 4 8 6
//
//b : -1 0 4 6
//     1 2 3
//         s
//           d
//
//sol = -1 / 0 / 4
//
//5 2 3 1 0 4 8 6
//
//b : 2 3
//    s
//      d
//
//sol = 2