Cod sursa(job #2034976)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 8 octombrie 2017 18:48:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define DIM 500041
using namespace std;

char buff[DIM];
int curs=0,n,k,v[DIM],maxi=-32000,ind;
deque <int> d;

void adv()
{
    curs++;
    if (curs >= DIM) {
        fread(buff, 1, DIM, stdin);
        curs = 0;
    }
}

int getInt()
{
    int nr=0,q=1;
    while(!(buff[curs]>='0' && buff[curs]<='9')) adv();
    if(buff[curs-1]=='-') q=-1;
    while(buff[curs]>='0' && buff[curs]<='9'){
        nr=nr*10 + buff[curs] - '0';
        adv();
    }
    return nr *q;
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    fread(buff, 1, DIM, stdin);
    n=getInt();
    k=getInt();
    for(int i=1;i<=n;i++)
        v[i]=getInt();
    d.push_back(1);
    for(int i=1;i<=n;++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){
            if(v[d.front()]>maxi){
                maxi=v[d.front()];
                ind=i;
            }
        }
    }
    cout<<ind-k+1<<" "<<ind<<" "<<maxi;
    return 0;
}