Cod sursa(job #1506480)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 20 octombrie 2015 18:41:59
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 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;
int main()
{
    fi>>n>>k;
    for (i=1; i<=n; i++) fi>>a[i];
    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