Cod sursa(job #1017786)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 28 octombrie 2013 13:44:29
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <deque>
using namespace std;

FILE * is = fopen("secventa.in", "r");
FILE * os = fopen("secventa.out", "w");

int n, k, w[500005];
int ii, jj, bmax;
int L, R;
deque <int> q;

int main()
{
    fscanf(is, "%d%d", &n, &k);
    for ( int i = 1; i <= n; ++i )
        fscanf(is, "%d", &w[i]);
    bmax = -30001;
    w[0] = -30001;
    for ( int i = 1; i <= k; ++i )
    {
        while ( !q.empty() && w[i] < w[q.back()] )
            q.pop_back();
        q.push_back(i);
        bmax = w[q.front()];
        ii = 1;
        jj = k;
    }
    for ( int i = k + 1; i <= n; ++i )
    {
        while ( !q.empty() && w[i] < w[q.back()] )
            q.pop_back();
        q.push_back(i);
        if ( i - q.front() + 1 > k )
            q.pop_front();
        if ( q.front() > bmax )
        {
            bmax = w[q.front()];
            ii = i - k + 1;
            jj = i;
        }
    }
    fprintf(os, "%d %d %d", ii, jj, bmax);
    fclose(is);
    fclose(os);
    return 0;
}

/*
while ( !q.empty() && w[i] < w[q.back()] )
            q.pop_back();
        while ( i - q.front() + 1 >= k )
            q.pop_back();
        q.push_back(i);
        if ( w[q.front()] > bmax && i >= k )
        {
            bmax = w[q.front()];

        }
*/