Cod sursa(job #744543)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 8 mai 2012 23:23:06
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cassert>
#include <cstdio>
#include <deque>

using namespace std;

const int nmax=500000, inf_n=-(1<<30);

int v[nmax+1];
deque <int> d;

int main(){
    int n, k, sol, sol_pos;

    assert(freopen("secventa.in", "r", stdin));
    assert(scanf(" %d %d ", &n, &k));
    
    sol=inf_n;
    for (int i=1; i<=n; ++i){
        assert(scanf(" %d ", &v[i]));
        if (d.front()==i-k){
            d.pop_front();
        }
        while (!d.empty()&&v[d.back()]>v[i]){
            d.pop_back();
        }
        d.push_back(i);
        if (i>k&&v[d.front()]>sol){
            sol=v[d.front()];
            sol_pos=i;
        }
    }
    fclose(stdin);

    assert(freopen("secventa.out", "w", stdout));
    printf("%d %d %d\n", sol_pos-k+1, sol_pos, sol);
    fclose(stdout);

    return 0;
}