Cod sursa(job #2045958)

Utilizator alisavaAlin Sava alisava Data 23 octombrie 2017 10:00:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

short a[500001];
deque<short>q;
queue<short>c;
char s[4000003];

void Push(short x)
{
    c.push(x);
    while(!q.empty()&&q.back()>x)
        q.pop_back();
    q.push_back(x);
}

void Pop()
{
    int x=c.front();
    if(x==q.front()) q.pop_front();
    c.pop();
}

int main()
{
    int n,k,i,st=1,dr;
    short x,maxim=-30005;
    fin>>n>>k;
    fin.get();
    fin.getline(s, 4000000);
    int semn = 1;
    n = 0;
    for (i = 0; s[i]; )
        if (s[i] == ' ') i++;
        else if (s[i] == '-') {semn = -1; i++;}
        else
        {
            x = 0;
            while ('0' <= s[i] && s[i] <= '9')
            {
                x = x * 10 + s[i] - '0';
                i++;
            }
            a[++n] = x * semn;
            semn = 1;
        }

    k--;
    dr=n;
    for(i=1;i<=k;i++)
        Push(a[i]);
     if (maxim<q.front())
        {
            maxim=q.front();
            st=i-k;
            dr=i;
        }
    for(i=i;i<=n;i++)
    {
        Push(a[i]);
        if (maxim<q.front())
        {
            maxim=q.front();
            st=i-k;
            dr=i;
        }
        Pop();
    }
    fout<<st<<" "<<dr<<" "<<maxim<<"\n";


    return 0;
}