Cod sursa(job #1930361)

Utilizator rexlcdTenea Mihai rexlcd Data 18 martie 2017 19:57:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

deque < int > q;
int v[500002];
char s[10000002];

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int n,k,ansi,ansj,ans=-30002;
    scanf("%d %d\n", &n, &k);
    fgets(s,10000002,stdin);
    int j=0,i=1;
    while(s[j]!=' ' && s[j]!='\n' && s[j]!='\0')
    {
        int val=0,ok=1;
        if(s[j]=='-')
        {
            ok=-1;
            j++;
        }
        else
            ok=1;
        while(isdigit(s[j]))
            val=val*10+(s[j++]-'0');
        j++;
        val*=ok;
        v[i++]=val;
    }
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && v[q.back()]>=v[i])
            q.pop_back();
        q.push_back(i);
        if(i-k>=0)
        {
            if(q.front()==i-k)
                q.pop_front();
            if(v[q.front()]>ans)
            {
                ans=v[q.front()];
                ansi=i-k+1;
                ansj=i;
            }
        }
    }
    printf("%d %d %d\n", ansi, ansj, ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}