Cod sursa(job #2229745)

Utilizator antracodsAntracod antracods Data 8 august 2018 01:23:18
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque <int> deck;

const int NMAX = 500000;
int v[NMAX+2];

int main()
{
    int n,k;
    in>>n>>k;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
    }
    for(int i=1;i<k;i++)
    {
        while(deck.empty()!=1 && v[i]<=v[deck.back()])
        {
            deck.pop_back();
        }
        deck.push_back(i);
    }
    int isol=k;
    int sol=-30001;
    for(int i=k;i<=n;i++)
    {
        while(deck.empty()!=1 && v[i]<=v[deck.back()])
        {
            deck.pop_back();
        }
        deck.push_back(i);
        while(deck.front()<=i-k)
        {
            deck.pop_front();
        }
        if(v[deck.front()]>sol)
        {
            sol=v[deck.front()];
            isol=i;
        }
    }
    out<<isol-k+1<<" "<<isol<<" "<<sol;
}