Cod sursa(job #2146977)

Utilizator bogdi1bogdan bancuta bogdi1 Data 28 februarie 2018 12:58:42
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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,maxx,st,dr,kk,semn,nn,nr;
    scanf("%d%d\n", &n, &k);
    gets(s);
    nn=strlen(s);
    kk=0;
    i=0;
    while(i<nn){
        if(s[i]=='-'){
            semn=s[i];
            i++;
        }
        if(s[i]>='0' && s[i]<='9'){
            nr=0;
            while(i<nn && s[i]>='0' && s[i]<='9'){
                nr=nr*10+s[i]-'0';
                i++;
            }
            if(semn=='-')
                nr*=-1;
            semn='+';
            v[++kk]=nr;
            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;
    dr=k;
    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;
            dr=i;
        }
    }
    printf("%d %d %d", st, dr, maxx);
    return 0;
}