Cod sursa(job #1510061)

Utilizator tudor00Stoiean Tudor tudor00 Data 24 octombrie 2015 15:25:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");
const int oo = (1<<30)-1;
deque<int> d;
int main()
{
    int n, k;
    int v[500001];
    in >> n >> k;
    for(int i=1 ; i<=n ; ++i)
        in >> v[i];

    for(int i=1 ; i<k ; ++i)
    {
        while(!d.empty() && v[i] < v[d.back()])
            d.pop_back();
        d.push_back(i);
    }
    int maxVal = -oo;
    int maxPos=0;
    for(int i=k ; i<=n ; ++i)
    {
        while(!d.empty() && v[i] < v[d.back()])
            d.pop_back();
        d.push_back(i);
        if(i-d.front() == k)
            d.pop_front();
        if(v[d.front()] > maxVal)
        {
            maxPos = i;
            maxVal = v[d.front()];
        }
    }

    out << maxPos-k+1 << ' ' << maxPos << ' ' << maxVal << '\n';

    in.close();
    out.close();
    return 0;
}