Cod sursa(job #2146995)

Utilizator bogdi1bogdan bancuta bogdi1 Data 28 februarie 2018 13:07:21
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
deque<int> dq;
int v[500005];
char s[3000005];
int main()
{   freopen("secventa.in", "r",stdin);
    freopen("secventa.out", "w",stdout);
    int n,k,i=0,maxx,st,kk=0,semn,nn,nr=0;
    scanf("%d%d\n", &n, &k);
    gets(s);
    nn=strlen(s);
    while(i<nn){
        semn=1;
        if(s[i]=='-'){
            semn=-1;
            ++i;
        }
        while(i<nn && s[i]>='0' && s[i]<='9'){
            nr=nr*10+s[i]-'0';
            ++i;
        }
        nr*=semn;
        v[++kk]=nr;
        nr=0;
        ++i;
    }
    dq.push_back(1);
    for(i=2; i<=k; ++i){
        while(!dq.empty() && v[dq.back()]>v[i])
            dq.pop_back();
        dq.push_back(i);
    }
    maxx=v[dq.front()];
    st=1;
    for(i=k+1; i<=n; ++i){
        while(!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        while(!dq.empty() && dq.front()<=i-k)
            dq.pop_front();
        dq.push_back(i);
        if(maxx<v[dq.front()]){
            maxx=v[dq.front()];
            st=i-k+1;
        }
    }
    printf("%d %d %d", st, st+k-1, maxx);
    return 0;
}