Cod sursa(job #889432)

Utilizator mihai27Mihai Popescu mihai27 Data 24 februarie 2013 15:15:06
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<deque>

using namespace std;

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

int j,final,x,i,n,k,sol=-70000;
deque<pair<int,int> > Q;
char c,s[500005];

int next()
{
    int nr=0,ok=0;

    while (s[j]==' ') j++;
    if (s[j]=='-')
    {
        j++;
        ok=1;
    }

    while (s[j]>='0' && s[j]<='9')
    {
        nr=nr*10+s[j]-'0';
        j++;
    }
    if (ok) return -nr;
    return nr;
}

int main()
{
    in>>n>>k;
    in.getline(s,500005);
    in.getline(s,500005);
    for (i=1;i<=n;i++)
    {
        x=next();

        while (Q.size() && Q.back().first > x)
            Q.pop_back();
        Q.push_back(make_pair(x,i));

        if (i>=k && Q.front().first>sol)
        {
            sol=Q.front().first;
            final=i;
        }

        if (i-Q.front().second+1==k)
            Q.pop_front();
    }
    out<<final-k+1<<' '<<final<<' '<<sol;
}