Cod sursa(job #1726214)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 7 iulie 2016 15:29:48
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

#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;

    fin>>n>>k;
    for( i = 1; i <= n; ++i )
        fin>>v[i];

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

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

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

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

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

    }

    fout<<begi<<" "<<endi<<" "<<ma;

    return 0;
}