Cod sursa(job #1307746)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 2 ianuarie 2015 19:23:11
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <deque>

using namespace std;

FILE *fin=freopen("secventa.in","r",stdin);
FILE *fout=freopen("secventa.out","w",stdout);

int n, k, start, finish, val = -30003;
int V[500003];
deque <int> D;


int main()
{
    scanf("%d%d", &n, &k);

    for(int i = 1 ; i <= n ; ++i )
    {
        scanf("%d", &V[i]);
        while( !D.empty() && V[D[D.size() - 1]] > V[i] )
            D.pop_back();
        D.push_back(i);
        while( i - D[0] >= k )
            D.pop_front();
        if(i >= k)
            if( V[D[0]] > val )
            {
                val = V[D[0]];
                finish = i;
                start = i - k + 1;
            }
    }

    printf("%d %d %d", start, finish, val);

    return 0;
}