Cod sursa(job #1661418)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 23 martie 2016 20:55:41
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<deque>

using namespace std;

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

deque <int> DQ;
int V[500005], S[500005];
int n, b, sol;
int const oo = 1000000000;

void Read()
{
    int i;

    f>>n>>b;
    for(i=1; i<=n; i++)
        f>>V[i];
}

void Solve()
{
    int i, idx;

    sol = -oo;
    DQ.push_back(1);
    for(i=2; i<=n; i++){
        if(DQ.back() == i - b)
            DQ.pop_back();
        while(DQ.size() && V[i] <= V[DQ.front()])
           DQ.pop_front();
        DQ.push_front(i);
        S[i] = V[DQ.back()];
        if(S[i] > sol && i >= b){
            sol = S[i];
            idx = i;
        }
    }
    g<<idx - b + 1<<" "<<idx<<" "<<sol<<"\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}