Cod sursa(job #2054096)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 1 noiembrie 2017 18:24:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream fi("secventa.in");
ofstream fo("secventa.out");
int n,k,i,A[500001],rez,poz,ind;
char S[3000005];
deque<int> Q;

int NextInt()
{
    int rez=0;
    int val;
    if(S[ind]=='-')
    {
        val=-1;
        ind++;
    }
    else
        val=1;
    while(S[ind]>='0' && S[ind]<='9')
        rez=rez*10+S[ind++]-'0';
    ind++;
    return rez*val;
}

int main()
{
    fi>>n>>k;
    fi.getline(S,1);
    fi.getline(S,3000001);
    ind=0;
    rez=-30000000;
    for(i=1; i<=n; i++)
    {
        A[i]=NextInt();
        while(!Q.empty() && i-Q.front()+1>k)
            Q.pop_front();
        while(!Q.empty() && A[Q.back()]>A[i])
            Q.pop_back();
        Q.push_back(i);
        if(i>=k)
        {
            if(rez<A[Q.front()])
            {
                rez=A[Q.front()];
                poz=i;
            }
        }
    }
    fo<<poz-k+1<<" "<<poz<<" "<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}