Cod sursa(job #1833896)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 23 decembrie 2016 14:36:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <deque>

using namespace std;

const int INF=1e9,dim=1<<17;

deque<int> q;
int v[500010],poz;
char pars[dim+1];

void inc()
{
    if(++poz==dim)
    {
        fread(pars,1,dim,stdin);
        poz=0;
    }
}

int citeste()
{
    for(;(pars[poz]<'0' or pars[poz]>'9') && pars[poz]!='-';inc());
    int s=0,p=1;
    if(pars[poz]=='-') {p=-1;inc();}
    for(;pars[poz]>='0' && pars[poz]<='9';inc())
        s=s*10+pars[poz]-'0';
    return s*p;
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,a,b,sol=-INF;
    fread(pars,1,dim,stdin);
    n=citeste();
    k=citeste();
    for(int i=1;i<=n;i++)
        v[i]=citeste();
    for(int i=1;i<=n;i++)
    {
        if(q.front()==i-k) q.pop_front();
        while(!q.empty() && v[q.back()]>=v[i]) q.pop_back();
        q.push_back(i);
        if(i>=k) if(v[q.front()]>sol) {sol=v[q.front()];a=i-k+1;b=i;}
    }
    printf("%d %d %d",a,b,sol);
    return 0;
}