Cod sursa(job #985253)

Utilizator gbi250Gabriela Moldovan gbi250 Data 17 august 2013 02:24:48
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <deque>
#include <climits>
#include <cctype>
#include <cstring>
#define SIZE 500002
using namespace std;

int i, n, k, pz, x, pos_elem, MAX=INT_MIN, v[SIZE], nr;
bool semn;
char s[SIZE*2];
deque <int> dq;

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%d %d ", &n, &k);
    gets(s);
    int len=strlen(s)-1;
    while(i<=len)
    {
        while(i<=len && s[i]!='-' && !isdigit(s[i]))
            ++i;
        if(s[i]=='-')
            semn=1, ++i;
        if(isdigit(s[i]))
        {
            nr=0;
            while(i<=len && isdigit(s[i]))
                nr=nr*10+s[i]-48, ++i;
            if(!semn)
                v[++x]=nr;
            else
                v[++x]=-nr;
            semn=0;
        }
    }
    for(i=1;i<=n;++i)
    {
        while(!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        while(!dq.empty() && i-k>=dq.front())
            dq.pop_front();
        dq.push_back(i);
        if(i>=k && v[dq.front()]>MAX)
        {
            MAX=v[dq.front()];
            pz=i-k+1;
        }
    }
    printf("%d %d %d", pz, pz+k-1, MAX);
    return 0;
}