Cod sursa(job #1626291)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 3 martie 2016 00:20:42
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
using namespace std;

#define DIM 500005

int v[DIM];
int Q[DIM];

int main()
{


    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    int n, i, j, s, p, t, d, k, ma, id, st, dr, begi, endi;

    scanf("%d%d",&n,&k);
    for( i = 1; i <= n; ++i )
        scanf("%d",&v[i]);

    ma = -(1<<23);
    dr = id = begi = endi = 0;
    st = 1;

    for( i = 1; i <= n; ++i ){

        while( st <= dr && Q[st] < i - k + 1  ) st++;

        while( st <= dr && v[Q[dr]] > v[i] ) dr--;
        dr++;
        Q[dr] = i;

        if( i - Q[st] + 1 >= k && v[Q[st]] > ma ){
            ma = v[Q[st]];
            begi = Q[st];
            endi = i;
        }

    }

    printf("%d %d %d",begi,endi,ma);

    return 0;
}