Cod sursa(job #1700591)

Utilizator leopop29Pop Leonard leopop29 Data 10 mai 2016 20:37:39
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <deque>
#define NM 500005

using namespace std;

deque<int> d;
int v[NM];

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");

    int n, k, mx = (1<<30)*-1, x, y;

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

    for(int p = 1; p <= n; ++p)
    {
        while(d.size() && v[d.back()] > v[p])
            d.pop_back();
        d.push_back(p);

        while(d.size() && d.front() <= p-k)
            d.pop_front();

        if(p >= k && v[d.front()] > mx)
        {
            mx = v[d.front()];
            x = p-k+1;
            y = p;
        }
    }

    g << x <<  ' ' << y << ' ' << mx;
}